回溯

回溯模板（三要素）

递归参数

plain

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

for循环为横向遍历过程

递归为组合答案过程

问题类型

组合问题

切割问题

切割范围为从startIndex ~ i，

子集问题

https://leetcode.cn/problems/subsets-ii/description/

额外添加变量判断是否相同（个人写法）

java

class Solution {
    List<List<Integer>> resList  = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int pre = -11; // 额外添加变量判断是否相同
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums,0);
        return resList;
    }
    public void backTracking(int[] nums, int start){
        resList.add(new ArrayList<>(list));

        for(int i = start;i < nums.length;i++){
            if(pre != nums[i]){
                list.add(nums[i]);
                backTracking(nums,i+1);
                list.remove(list.size() - 1);
                pre = nums[i];
            }
        }
    }
}

不需要添加变量判断是否相同（灵神写法）

java

class Solution {
    List<List<Integer>> resList  = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums,0);
        return resList;
    }
    public void backTracking(int[] nums, int start){
        resList.add(new ArrayList<>(list));

        for(int i = start;i < nums.length;i++){
            if(i>start && nums[i] == nums[i-1]){
                continue;
            }
            list.add(nums[i]);
            backTracking(nums,i+1);
            list.remove(list.size() - 1);
        }
    }
}

https://leetcode.cn/problems/non-decreasing-subsequences/description/

进一步理解****

****

java

class Solution {
    List<List<Integer>> resList  = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums,0);
        return resList;
    }
    public void backTracking(int[] nums,int start){
        if(list.size() >= 2){
            resList.add(new ArrayList<>(list));
        }
        int[] flag = new int[201];
        for(int i = start;i<nums.length;i++){
            if(list.size() > 0 && list.get(list.size() - 1) > nums[i]){
                continue;
            }else if(i>start && nums[i] == nums[i-1]){
                continue;
            }
            if(flag[nums[i] + 100] == 0){
            flag[nums[i] + 100]++;
            list.add(nums[i]);
            backTracking(nums,i+1);
            list.remove(list.size() - 1);
            }
        }
    }
}

全排列问题

全排列问题中当横向需要去重，纵向需要防止一个元素多次使用，我们需要借助一个数组来记录当前节点是否被访问

java

class Solution {
    List<List<Integer>> resList  = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] flag = new boolean[8];
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums);
        return resList;
    }
    public void backTracking(int[] nums){
        if(list.size() == nums.length){
            resList.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i< nums.length;i++){
            if(i > 0 && nums[i] == nums[i-1] && !flag[i-1]){
                continue;
            }
            if(!flag[i]){
            flag[i] = true;
            list.add(nums[i]);
            backTracking(nums);
            list.remove(list.size() - 1);
            flag[i] = false;
            }
           
        }
    }
}

回溯 ​

回溯模板（三要素） ​

问题类型 ​

回溯

回溯模板（三要素）

问题类型