39. 組合總和

39. 組合總和 - 力扣（LeetCode）
本題和之前組合題不同在于，可以取重復(fù)的值，那么for循環(huán)里的遞歸還是從i開始，另外沒有規(guī)定取k個(gè)，那么遞歸結(jié)束條件就是sum==target即可，另外剪枝操作是先將數(shù)組排序，然后在for循環(huán)里加條件，如果sum>target就break，注意這個(gè)地方和之前的組合總和3不同

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        backTracking(candidates, target, 0, 0);
        return result;
    }

    public void backTracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i=startIndex; i<candidates.length; i++) {
            sum += candidates[i];
            if (sum > target) break;
            path.add(candidates[i]);
            //因?yàn)槭强梢灾貜?fù)的，所以從i開始
            backTracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

40.組合總和II

40. 組合總和 II - 力扣（LeetCode）
本題要求數(shù)組中可以有重復(fù)數(shù)值，但是最后的結(jié)果中不能有重復(fù)的組合，所以中間過程需要去重，先把數(shù)組排序，進(jìn)行數(shù)層去重，比如兩個(gè)1相鄰，第一個(gè)1遍歷后，第二個(gè)1就可以不用遍歷了，因?yàn)榈谝粋€(gè)1遍歷的過程已經(jīng)包含了第二個(gè)1遍歷的結(jié)果

class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public List<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];   
        Arrays.fill(used, false);
        Arrays.sort(candidates);
        backTracking(candidates, target, 0, 0);
        return result;
    }

    public void backTracking(int[] candidates, int target, int sum, int startIndex) {
        //這里沒有return結(jié)束，因?yàn)閏andidates里有重復(fù)的值，后面可能還會(huì)有結(jié)果
        if (sum == target) {
            result.add(new ArrayList<>(path));
        }
        for (int i = startIndex; i < candidates.length; i++) {
            //去重：used=true代表在樹枝上有重復(fù)的值，不需要去重；used=false代表在數(shù)層上有重復(fù)的值，又是回溯產(chǎn)生的，需要去重
            if (i > 0 && candidates[i] == candidates[i-1] && !used[i-1]) {
                continue;
            }
            sum += candidates[i];
            if (sum > target) {
                break;
            }
            used[i] = true;
            path.add(candidates[i]);
            backTracking(candidates, target, sum, i+1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

131.分割回文串

131. 分割回文串 - 力扣（LeetCode）
本題在判斷分割的字符串是回文子串后，將其加入path中，并且將判斷分割到最后是否合格的過程，放到for循環(huán)中

class Solution {

    List<String> path = new LinkedList<>();
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return result;
    }

    public void backTracking(String str, int startIndex) {
        if (startIndex >= str.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < str.length(); i++) {
            if (isPalindrome(str, startIndex, i)) {
                String str1 = str.substring(startIndex, i + 1);
                path.add(str1);
            } else {
                continue;
            }
            backTracking(str, i + 1);
            path.removeLast();
        }
    }

    // 判斷是否是回文子串，左閉右閉區(qū)間
    public boolean isPalindrome(String str, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}