39. 组合总和 40.组合总和II 131.分割回文串

39. 组合总和

自己写的回溯算法：

class Solution {
    List<List<Integer>> list;
    LinkedList<Integer> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        list = new ArrayList<>();
        res = new LinkedList<>();
        f(candidates,target,0);
        return list;
    }
    void f(int[] candidates,int target,int idx){
        if(target == 0){
            list.add(new ArrayList(res));
            return;
        }
        for(int i = idx;i < candidates.length;i++){
            if(target < 0) break;
            res.add(candidates[i]);
            f(candidates,target - candidates[i],i);
            res.removeLast();
        }
    }
}

优化，剪枝操作：

class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
       List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
}

40.组合总和II

去重关键：

if(i > idx && candidates[i] == candidates[i-1]) continue;

class Solution {
    List<List<Integer>> list;
    List<Integer> res;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        list = new ArrayList<>();
        res = new ArrayList<>();
        Arrays.sort(candidates);
        f(candidates,target,0,0);
        return list;
    }
    void f(int[] candidates,int target,int sum,int idx){
        if(sum == target){
            list.add(new ArrayList(res));
            return;
        }
        for(int i = idx;i < candidates.length;i++){
        //这行代码去重关键，因为candidates是有序的
            if(i > idx && candidates[i] == candidates[i-1]) continue;
            if(sum + candidates[i] > target) break;
            res.add(candidates[i]);
            f(candidates,target,sum + candidates[i],i + 1);
            res.remove(res.size() - 1);
        }
    }
}

用标识判断：

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

class Solution {
    List<List<Integer>> list;
    List<Integer> res;
    boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        list = new ArrayList<>();
        res = new ArrayList<>();
        Arrays.sort(candidates);
        f(candidates,target,0,0);
        return list;
    }
    void f(int[] candidates,int target,int sum,int idx){
        if(sum == target){
            list.add(new ArrayList(res));
            return;
        }
        for(int i = idx;i < candidates.length;i++){
            if(sum + candidates[i] > target) break;
            //判断是否是同一层
            if(i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            res.add(candidates[i]);
            f(candidates,target,sum + candidates[i],i + 1);
            used[i] = false;
            res.remove(res.size() - 1);
        }
    }
}

131.分割回文串

回溯法：

class Solution {
    List<List<String>> list;
    LinkedList<String> res;
    public List<List<String>> partition(String s) {
        list = new ArrayList<>();
        res = new LinkedList<>();
        f(s,0);
        return list;
    }
    void f(String s,int startIndex){
        if(startIndex == s.length()){
            list.add(new ArrayList(res));
            return;
        }
        for(int i = startIndex;i < s.length();i++){
            if(isP(s,startIndex,i)){
                res.add(s.substring(startIndex,i+1));
            }else{
                continue;
            }
            f(s,i+1);
            res.removeLast();
        }
    }
    boolean isP(String s,int startIndex,int end){
        for(int i = startIndex,j = end;i <= j;i++,j--){
            if(s.charAt(i) == s.charAt(j)){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }
}