Combination

• 问题模型：求出所有满足条件的组合
• 判断条件：组合中的元素是顺序无关的
• 分析方法：构建深度优先搜索树+判断可行解
• 模板：Permutations & Subsets
• 时间复杂度：与2^n相关 (或者n!)，为O(答案个数*构造每个答案的时间)

Implementaion

• 通常用递归实现
  • 注意搜索的回溯（回到上一层），paths.remove(path.size()-1)
    • 注意，是object类型的才需要回溯，如果是String等基本类型，不需要
  • 加入结果集合中需要进行shallow copy new ArrayList<>(path)
• 几种特殊情况
  • 是否需要排序
  • 是否有重复元素
    • 先排序 Arrays.sort(nums)
    • 去重：if (i != pos && nums[i] == nums[i-1]) continue;
  • 每个元素是否允许多次选择
    • 搜索时候从index开始，而不是从index+1

Template

//Subset Question
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();

    if (nums == null) {
        return results;
    }

    if (nums.length == 0) {
        results.add(new ArrayList<Integer>());
        return results;
    }

    Arrays.sort(nums);
    helper(new ArrayList<Integer>(), nums, 0, results);
    return results;
}
//递归的定义：在nums中，找到所有以subset开头的集合，并放到results
private void helper(ArrayList<Integer> subset, int[] nums, int startIndex, List<List<Integer>> results) {
    result.add(new ArrayList<Integer>(subset));
    for (int i = startIndex; i < nums.length; i++) {
        subset.add(nums[i]);
        helper(subset, nums, i+1, results);
        subset.remove(subset.size()-1);
    }
}

Subset

• 找所有可能的子集 （组合）

Analysis

• 所有解: DFS
• 顺序matters（组合），如何保证不重复取
  • 对于Array，引入pos来排除已经选过的
• 添加到最终结果的时候，需要深拷贝

Subset II

• 先排序，再排除重复数字if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates

Permutations

• 找所有可能的排列

Analysis

• 所有解: DFS
• 顺序不同排列不同，
  • recursion退出的条件是排列的长度=原数组长度
  • 添加到path之前需要判断是否已经存在
• 添加到最终结果的时候，需要深拷贝
• 时间复杂度n!

  每

你用解集数来估计得到的结果也是一样的：N个数的全排列是N!种，故共有N!个解，每个解需要O(N)时间构造，所以总时间是O(N!*N)

这和1中的节点分析不矛盾。Permutations的解空间树是一棵"complete"的树（对于第K层的任意节点，一定有N-k个children），而Subsets的解空间树则非常稀疏。

• 总共depth为n，每一层分别有n,n-1,n-2,...种排列的可能
• 因为为n!，所以n不会很大，此时用list.contains虽然操作是O(n)的，但是也是可以接受的，这样能让代码更简单

Permutations II

• 包含重复的值，需要通过排序+visited数组来排除
• 这里如果前一个数一样，考虑前一个数是否用过，如果用过了，那么当前的数可以继续加到结果集里。否则需要跳出。注意这是在backtracking的每一层中进行判断，到下一层recursion中，前一个数就没有用过了，那么当前的数就不需要再作为起点构建一个结果集（属于重复的case）

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length == 0) return result;
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        helper(nums, new ArrayList<>(), result, visited);

        return result;
    }

    public void helper(int[] nums, List<Integer> list, List<List<Integer>> result, boolean[] visited) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue;

            list.add(nums[i]);
            visited[i] = true;
            helper(nums, list, result, visited);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }

Combination Sum

• 找到所有满足条件(sum)的组合
• 每个数可以用若干次，所以下一个recursion的pos不需要+1

Analysis

• 所有解：DFS
• 不同之处
  • target的限制
  • target一直在变化
• 注意题目的要求，Candidates是否允许重复的元素
  • 允许重复的情况下，在取下一层dfs的时候不需要+1，即允许重用当前的元素
• 是否需要提前sort
  • 当需要去重的时候
  • 当DFS中，遇到超过target的元素时，可以直接return，否则需要continue

Combination Sum II

• 每个元素只能用一次
• 需要排除if (i != pos && candidates[i] == candidates[i-1]) continue;

Palindrome Partitioning

• 分割String使得每一部分都变成一个回文子序列
• 与前面不同的是
  • 退出条件是pos==len
  • 每次pos的变化不是简单的pos+1,而是与取了前几个有关即i+1
• Time Complexity
  • O(2^n * n) since check palindrome take O(n)
• follow up
  • 优化时间，先用一个二维数组[i][j]保存i-j之间的str是否为回文，DFS的过程中保存的是i，最后需要在组成结果的时候进行特殊处理

Palindrome Partitioning II

动态规划