多向递归

• 子集
  • 二叉树遍历解法
  • 组合数解法
• 子集 II
  • 二叉树遍历解法
  • 组合数解法
• 数字组合
  • 二叉树遍历解法
  • 组合数解法

子集

二叉树遍历解法

递归的定义

• helper(nums, start, end, combinations, combination)

• =>

• helper(nums, start, combinations, combination)

递归的拆解

• 选取第 start 个数

• 不选第 start 个数

递归的出口

• start ~ end 区间为空的时候

• =>

• start 越出 nums 范围的时候

void combine(int[] nums, int i, 
          List<Integer> comb, 
          List<List<Integer>> combs) {
    if (i == nums.length) {
        combs.add(new ArrayList<>(comb));
        return;
    }
    
    combine(nums, i + 1, comb, combs);
    
    comb.add(nums[i]);
    combine(nums, i + 1, comb, combs);
    comb.remove(comb.size() - 1);
}

组合数解法

nums 的全子集

• C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, n)

如何得到 C(n, i)

• C(n, 1) => C(n, 0) 的基础上加一个数

• C(n, 2) => C(n, 1) 的基础上加一个数

• C(n, 3) => C(n, 2) 的基础上加一个数

•...

• C(n, i) => C(n, i - 1) 的基础上加一个数

void combine(int[] nums, int i, 
          List<Integer> comb, 
          List<List<Integer>> combs) {
	combs.add(new ArrayList<>(comb));
    
    for (int j = i; j < nums.length; j++) {
        comb.add(nums[j]);
        combine(nums, j + 1, comb, combs);
        comb.remove(comb.size() - 1);
    }
}

1. 状态的转移放在了for循环里
2. 递归的隐式出口

子集II

 排列问题递归树

带重复元素的排列

 如何从全排列问题转化过来

第k个排列

 求解第k个排列

 求解一个排列是第几个排列

下一个排列

全排列

递归的定义

• helper(nums, permutations, permutation, visited)

• 不需要 start 和 end 两个指针

nums：1 2 3

递归的拆解

• 在 nums 里选择一个还未选择的数

递归的出口

• 所有数都被选中的时候

• visited 的大小达到了 length

• permutation 的大小达到了 length

void permute(int[] nums, Set<Integer> seen,
          List<Integer> perm, 
          List<List<Integer>> perms) {
    if (perm.size() == nums.length) {
        perms.add(new ArrayList<>(perm));
        return;
    }
    
    for (int num : nums) {
        if (seen.contains(num)) continue;
        
        perm.add(num);
        seen.add(num);
        permute(nums, seen, perm, perms);
        perm.remove(perm.size() - 1);
        perm.remove(num);
    }
}