欢迎大家来到IT世界,在知识的湖畔探索吧!

什么是排列！什么是组合?

排列是有序的，组合是无序的

1，2，3 1，3，2 是两种排列，但是只是一种组合。

回溯算法

void backtrack(结果list, 一个符合条件的结果list（路径list）, 原输入数组nums){

}

先判断递归结束条件

if(结果list 的长度和输入数组长度一样){

这个结果有效，把他放入二维结果数组里面

返回

}

遍历输入数组

如果这个数字用过了，就跳过这个循环(不能重复问题)

继续下一个循环，加入别的数字

做回溯递归，改变变量，这是在for循环里面递归

移出最后一个添加的元素；

class Solution {


    List<List<Integer>> res;//结果
    List<Integer> path;//路径
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();//结果
        List<Integer> path = new ArrayList<>();;//路径
        // Arrays.sort(nums); // not necessary
       
        backtrack(res, path, nums);
        return res;
    }
    
    private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums){
        if(nums.length == path.size()){
            // res.add(path);
            res.add(new ArrayList<>(path));//这里要new， 不然返回的都是空数组，java 是值传递。
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(path.contains(nums[i])){ //list 有contains 方法。 这里也可以用used[] 数组判断
                continue;
            }
            path.add(nums[i]);
            backtrack(res, path, nums);
            path.remove(path.size() - 1);
        }
    }

}

欢迎大家来到IT世界,在知识的湖畔探索吧!

• 时间复杂度：O(N×N!)

//递归前后代码是对称操作。

欢迎大家来到IT世界,在知识的湖畔探索吧!class Solution {    public List<List<Integer>> permuteUnique(int[] nums) {    // List<List<Integer>> res;//结果    // List<Integer> path;//路径           List<List<Integer>> res = new ArrayList<>();//结果        List<Integer> path = new ArrayList<>();;//路径        Arrays.sort(nums); //necessary               backtrack(res, path, nums, new boolean[nums.length]);        return res;    }        private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, boolean used[]){        if(nums.length == path.size()){            // res.add(path);            res.add(new ArrayList<>(path));//这里要new， 不然返回的都是空数组，java 是值传递。            return;        }        for(int i = 0; i < nums.length; i++){                        if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;            // if(path.contains(nums[i])){ //list 有contains 方法。 这里也可以用used[] 数组判断            //     continue;            // }            path.add(nums[i]);            used[i] = true;            backtrack(res, path, nums, used);            used[i] = !used[i];            path.remove(path.size() - 1);                    }    }}

去重判断：

if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i – 1]) continue;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // Arrays.sort(nums);//先排序
        backtrack(res, path, nums, 0);
        return res;


    }
    private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int start){
        if(start > nums.length){
            return;
        }
        res.add(new ArrayList<>(path));//加入结果，先加入一个空集

        for(int i = start; i< nums.length; i++){
            path.add(nums[i]);
            //回溯加另一个分支（自己画一个树形结构，排列组合），回溯做另一个选择
            backtrack(res, path, nums, i + 1); // 注意从i+1开始，元素不重复取
            //撤销选择
            path.remove(path.size()-1);//移除最后一位元素，上一次加入数组的（画出树形图好理解）
        }
    }


}

组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

—-参考《代码随想录》

再做回溯时候加两行代码就可以，跳过重复元素。

排序， i 和 i-1 位置元素一样，跳过i 位置

if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates

欢迎大家来到IT世界,在知识的湖畔探索吧!class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {


        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);//先排序,不然这样的没法去重,[4,4,4,1,4]
        backtrack(res, path, nums, 0);
        return res;


    }
    private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int start){
        if(start > nums.length){
            return;
        }
        res.add(new ArrayList<>(path));//加入结果，先加入一个空集

        for(int i = start; i< nums.length; i++){
            //去重
            if(i > start && nums[i] == nums[i-1]){
                continue;
            }


            path.add(nums[i]);
            //回溯加另一个分支（自己画一个树形结构，排列组合），回溯做另一个选择
            backtrack(res, path, nums, i + 1); // 注意从i+1开始，元素不重复取
            //撤销选择
            path.remove(path.size()-1);//移除最后一位元素，上一次加入数组的（画出树形图好理解）
        }
    }


}