力扣labuladong一刷day66天回溯大集合

力扣labuladong一刷day66天回溯大集合

一、40. 组合总和 II

题目链接：https://leetcode.cn/problems/combination-sum-ii/description/
思路：本题属于：有重复元素，不可复选的类型，要求结果集不可重复。如1,1,1，1正常不采取其他措施就会出现，1,1和1,1的情况，这种问题的根源就是有多个重复的元素，你在左孩子里用了，右孩子里又使用了，这就重复了，我们需要做的就是同一树层，相同的元素你前面选了后面就不能再选了，选了就可能出现重复，所以要避免这种情况。
这叫树层去重，即横向去重，纵向不去重，只需要 if (j > i && nums[j] == nums[j-1]) continue;即可起到去重的效果。

class Solution {
   List<List<Integer>> arrayLists;
    List<Integer> list;
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        arrayLists = new ArrayList<>();
        list = new ArrayList<>();
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return arrayLists;
    }

    void backTracking(int[] nums, int target, int i) {
        if (sum == target) {
            arrayLists.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j < nums.length && sum+nums[i] <= target; j++) {
            if (j > i && nums[j] == nums[j-1]) continue;
            sum += nums[j];
            list.add(nums[j]);
            backTracking(nums, target, j+1);
            sum -= nums[j];
            list.remove(list.size()-1);
        }
    }
}

二、131. 分割回文串

题目链接：https://leetcode.cn/problems/palindrome-partitioning/description/
思路：分割和组合就是一个意思，没什么区别

class Solution {
   List<List<String>> arrayLists;
    List<String> list;
    public List<List<String>> partition(String s) {
        arrayLists = new ArrayList<>();
        list = new ArrayList<>();
        backTracking(s, 0);
        return arrayLists;
    }
    void backTracking(String s, int index) {
        if (index == s.length()) {
            arrayLists.add(new ArrayList<>(list));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (!isTrue(s, index, i)) continue;
            list.add(s.substring(index, i+1));
            backTracking(s, i+1);
            list.remove(list.size()-1);
        }
    }
    boolean isTrue(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}