代码随想录算法训练营day26|39. 组合总和、40. 组合总和||、8.分割回文串

39. 组合总和

由题意可知，数组中的每一个数都可以重复相加，因此我们在绘制树形图的时候，每次取完某一个数，下一次回溯的时候还可以用该数，比如2、3、6，每次取完2，候选还剩2、3、6。而最后答案也确实是2、2，所以2每次取完不能排除。
另外对于存储满足条件结果的path，每次从纵向的回溯过程出来之后，要将这一层回溯加进去的值减掉给横向的循环的下一个值腾出空间，一边进入下一个值的回溯。同时要给一个sum的值记录和。

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length == 0 || candidates == null) return res;
        backTracking(candidates,target,0,0);
        return res;
    }
    public void backTracking(int[] candidates, int target,int sum,int startIndex){
        if(sum > target) return;
        if(sum == target) res.add(new ArrayList<Integer>(path));
        //循环
        for(int i = startIndex;i < candidates.length;i++){
            sum += candidates[i];
            path.add(candidates[i]);
            backTracking(candidates,target,sum,i);
            sum -= candidates[i];
            path.remove(path.size()-1);
        }
    }
}

40. 组合总和||

我觉得这道题目卡个2讲的已经够好了，多看几遍理解透彻就行。主要就是需要对candidates进行排序，然后理解去重的条件为什么是：

      if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
        continue;
      }

最后的代码是：
其中：used是用来记录该位置的candidates的值是否被用过

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();
    int sum = 0;
    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);
        return res;
    }
    public void backTracking(int[] candidates, int target,int startIndex){
        if(sum == target) res.add(new ArrayList<Integer>(path));
        for(int i = startIndex;i < candidates.length;i++){
                if(sum + candidates[i] > target){
                    break;
                }
            // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
                if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                    continue;
                }
            sum += candidates[i];
            used[i] = true;
            path.add(candidates[i]);
            backTracking(candidates,target,i+1);
            sum -= candidates[i];
            used[i] = false;
            path.remove(path.size()-1);
        }
    }
}

8.分割回文串

class Solution {
     List<List<String>> res = new ArrayList<List<String>>();
    ArrayList<String> path = new ArrayList<String>();
    public List<List<String>> partition(String s) {
        backTracking(s,0);
        return res;
    }
    public void backTracking(String s,int startIndex){
        //如果起始值到达字符串末尾，结束递归
        if(startIndex >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if(judgeHuiWen(s,startIndex,i)){
                path.add(s.substring(startIndex,i+1));
            }else{
                continue;//有一个子字符串不是回文字符串就没有必要进行回溯了
            }
            //如果现层的子字符串为回文的，继续回溯
            backTracking(s,i+1);//i往下一位，继续回溯
            //回溯
            path.remove(path.size()-1);
        }

    }
    public boolean judgeHuiWen(String s,int startIndex,int endIndex){
        while(startIndex <= endIndex){
            if(s.charAt(startIndex) != s.charAt(endIndex)) return false;
            startIndex++;
            endIndex--;
        }
        return true;
    }
}