欢迎关注个人公众号：爱喝可可牛奶

LeetCode算法训练-回溯 491.递增子序列 46.全排列 47.全排列 II

LeetCode 491. 递增子序列

分析

找出并返回所有数组中不同的递增子序列

1. 绝对不能先升序 绝对不能先升序 绝对不能先升序 这样会改变原有数组的结构

2. 子序列中元素在数组中不一定相邻

3. 只要叶子节点，也就是path，一满足条件，直接加入res

4. 注意去重used[] 数组只针对当前节点的后序节点 要在回溯函数中定义 画回溯树一看便知

代码

class Solution {
    private LinkedList path = new LinkedList();
    private List> res = new ArrayList();
    public List> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return res;
    }

    private void backtracking (int[] nums, int start) {
        // 保证了能进入path的元素是升序的
        if (path.size() > 1) {
            res.add(new LinkedList(path));
            // 注意这里不要加return，要取树上的节点
        }
        // 元素值为used数组索引 只对同一行进行去重 
        int[] used = new int[201];
        for (int i = start; i 

LeetCode 46. 全排列

分析

全排列，收集回溯树的叶子节点即可 注意终止条件要return

But 因为搜索过程每次都从第一个元素开始，要记录哪些元素已经使用过了 used[]数组应该是全局的

代码

class Solution {

    List> result = new ArrayList();// 存放符合条件结果的集合
    LinkedList path = new LinkedList();// 用来存放符合条件结果
    boolean[] used;
    public List> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i 

LeetCode 47. 全排列 II

分析

按任意顺序 返回所有不重复的全排列

涉及到如何去重 根据用例画一个回溯树看看

在横向遍历时，如果当前元素==前一个元素，continue；

难点：如何判断统一树层当前节点的前一个节点使用过 去看一下当前节点前一个节点的状态

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

代码

class Solution {

    List> result = new ArrayList();// 存放符合条件结果的集合
    LinkedList path = new LinkedList();// 用来存放符合条件结果
    
    public List> permuteUnique(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        // 得先排个序才能保证前后元素比较的正确性
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        permuteHelper(nums,used);
        return result;
    }

    private void permuteHelper(int[] nums, boolean[] used){
        if (path.size() == nums.length){
            result.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i  0 && nums[i] == nums[i-1] && !used[i-1]){
                continue;
            }
            if (!used[i]){
                used[i] = true;
                path.add(nums[i]);
                permuteHelper(nums,used);
                path.removeLast();
                used[i] = false;
            }

        }
    }
}

总结

1. 组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果
2. 理清回溯树树层、树枝的节点关系 for循环处理的是树层，递归调用函数处理的是树枝
3. 如果没有startIndex来确定取的是数组中哪一个元素，used[]数组+for循环能间接确定这个元素是不是取过