Subset & Combination & Combination Sum & Permutations
Subset和Combination类的题目是DFS + Backtracking最经典基础的应用，所以我们首先做。
1. 尝试可能性（放）
2. 递归
3. Backtracking，反向操作（擦除）
注意要先排序（如果对顺序有要求的话
78. Subsets / Subsets
不变的经典
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
List<Integer> subset = new ArrayList<>();
dfs(result, subset, nums, 0);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> subset,
int[] nums, int start) {
result.add(new ArrayList<Integer>(subset));
for (int i = start; i < nums.length; ++i) {
subset.add(nums[i]);
dfs(result, subset, nums, i + 1);
subset.remove(subset.size() - 1);
}
}
}
90. Subsets II
比如说[1,2,2] 我们是允许[2,2]这样的subset，但是[2]这样的subset却不能出现两次，所以查重时向前查重，如果和前面的重复了就continue跳过。
这就带来了一个新的细节，先排序。
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
List<Integer> subset = new ArrayList<>();
dfs(result, subset, nums, 0);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> subset,
int[] nums, int start) {
result.add(new ArrayList<Integer>(subset));
for (int i = start; i < nums.length; ++i) {
if (i != start && nums[i] == nums[i - 1]) continue;
subset.add(nums[i]);
dfs(result, subset, nums, i + 1);
subset.remove(subset.size() - 1);
}
}
}
77. Combinations / Combinations
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
if (k == 0) return result;
List<Integer> list = new ArrayList<>();
dfs(result, list, 1, n, k);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list,
int start, int n, int k) {
if (list.size() == k) result.add(new ArrayList<Integer>(list));
for (int i = start; i <= n; ++i) {
list.add(i);
dfs(result, list, i + 1, n, k);
list.remove(list.size() - 1);
}
}
}
39. Combination Sum
元素能用无限次，输入没有重复，输出不能重复。
元素可以重复选用，传进去的 index 可以以 i 为准。（过去我们传入的都是i + 1）
但是还是不能走回头路，不然会有重复答案。
所有元素为正整数非常重要，要么这题可能有无数个解。
这道题和下面lintcode那个不一样，输入没有重复，如果你硬要用重复testcase去测试，就会出现这样的悲剧：
这个题实际上就是无限背包问题，backpack IV和backpack VI都和这题非常像。IV和VI两道题都是无限取用，指定一个target把背包装满，问有多少种方式。不同之处在于VI允许组合重合顺序不重合的方案，比如说[2,3,6,7]，IV只有两个解法，[7]和[2,2,3]，和本题的要求是相同的，而VI可以是[7],[2,2,3],[2,3,2],[3,2,2]。而这两道背包问题和本题的根本区别在于，背包问题是求方案的个数，本题求的是所有方案。这就回到了以前那个说过的问题，背包问题属于动态规划的一个分支，而在求具体方案而不是求方案总数时，我们不能使用动规，也就是说本题是无法用DP来解的。反过来讲，背包问题却可以用DFS来解（理论上，尤其是backpack VI，但是要注意的是，DFS在背包问题的使用可能会造成栈溢出，这个和具体的testcase和环境有关。
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) return result;
List<Integer> list = new ArrayList<>();
dfs(result, list, candidates, target, 0, 0);
return result;
}
private void dfs (List<List<Integer>> result, List<Integer> list,
int[] nums, int target, int sum, int start) {
if (sum > target) return;
if (sum == target) result.add(new ArrayList<Integer>(list));
for (int i = start; i < nums.length; ++i) {
list.add(nums[i]);
dfs(result, list, nums, target, sum + nums[i], i);
list.remove(list.size() - 1);
}
}
}
Combination Sum
元素能用无限次，输入有重复，输出不能重复。
Lintcode上面这道题要比上面leetcode那道更严谨一点，不过这都跟输入的input有关，如果lc已经说了我们不会有重复数字在input中，那[2,2,3] 7这样的testcase我们本来也就不用考虑。Combination Sum这几道题有微妙的不同，代码间改动很小。
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) return result;
Arrays.sort(candidates);
List<Integer> list = new ArrayList<>();
dfs(result, list, candidates, target, 0, 0);
return result;
}
private void dfs (List<List<Integer>> result, List<Integer> list,
int[] nums, int target, int sum, int start) {
if (sum > target) return;
if (sum == target) {
List<Integer> newList = new ArrayList<Integer>(list);
Collections.sort(newList);
result.add(newList);
return;
}
for (int i = start; i < nums.length; ++i) {
if (i != start && nums[i] == nums[i - 1]) continue;
list.add(nums[i]);
dfs(result, list, nums, target, sum + nums[i], i);
list.remove(list.size() - 1);
}
}
}
40. Combination Sum II
元素只能用一次，输入有重复，输出不能重复。
没重复元素，想避免重复解，用 index 单调向前。
有重复元素，想避免重复解，每次和前一个元素相同，continue跳过。
39 40这两道题和78 90是异曲同工的，对于重复元素的处理都是同样的continue跳过。所以说subsets是不变的经典，DFS + Backtracking的灵魂。
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) return result;
Arrays.sort(candidates);
List<Integer> list = new ArrayList<>();
dfs(result, list, candidates, target, 0, 0);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list,
int[] nums, int target, int sum, int start) {
if (sum > target) return;
if (sum == target) result.add(new ArrayList<Integer>(list));
for (int i = start; i < nums.length; ++i) {
if (i != start && nums[i] == nums[i - 1]) continue;
list.add(nums[i]);
dfs(result, list, nums, target, sum + nums[i], i + 1);
list.remove(list.size() - 1);
}
}
}
216. Combination Sum III
Trivial problem
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
if (k == 0) return result;
List<Integer> list = new ArrayList<>();
dfs(result, list, 0, k, n, 1);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list,
int sum, int k, int n, int start) {
if (sum > n || list.size() > k) return;
if (list.size() == k && sum == n) result.add(new ArrayList<Integer>(list));
for (int i = start; i < 10; ++i) {
list.add(i);
dfs(result, list, sum + i, k, n, i + 1);
list.remove(list.size() - 1);
}
}
}
377. Combination Sum IV / Backpack VI
就像我前面说的，这个题实际上就是Backpack VI，这道题最好的方式就是用DP来解，因为求的是方案总数而不是具体方案，但是DFS + Backtracking的方法是比较通用的，缺点也很明显，在这里，当32的时候就会出现TLE和MLE，方案数为39882198。DFS会造成栈溢出。我把大概的思路写在下面，这个倒没有什么难点。就注意一个地方，因为这里是无限取用且不计重复，每次都要从0开始重新推演，这样才会出现(1, 1, 2)，(1, 2, 1)，(2, 1, 1)这样的结果，所以我们不需要index。
public class Solution {
public int combinationSum4(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0) return 0;
List<Integer> list = new ArrayList<>();
dfs(result, list, candidates, target, 0);
return result.size();
}
private void dfs(List<List<Integer>> result, List<Integer> list,
int[] nums, int target, int sum) {
if (sum > target) return;
if (sum == target) result.add(new ArrayList<Integer>(list));
for (int i = 0; i < nums.length; ++i) {
list.add(nums[i]);
dfs(result, list, nums, target, sum + nums[i]);
list.remove(list.size() - 1);
}
}
}
下面是DP做法，思路我写在Backpack了。
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int j = 0; j < nums.length; ++j) {
if (i >= nums[j]) f[i] += f[i - nums[j]];
}
}
return f[target];
}
}
46. Permutations / Permutations
元素排列，输入没有重复，输出不能重复
都是简单套路和小变形。这次每轮dfs都考虑所有元素（所以不用传 index 参数了），每次看一下list里面是不是已经有这个元素了。或者传个 boolean array 只挑没用过的数字也行。
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
List<Integer> list = new ArrayList<>();
dfs(result, list, nums);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list,
int[] nums) {
if (list.size() == nums.length) result.add(new ArrayList<Integer>(list));
for (int i = 0; i < nums.length; ++i) {
if (list.contains(nums[i])) continue;
list.add(nums[i]);
dfs(result, list, nums);
list.remove(list.size() - 1);
}
}
}
47. Permutations II / Permutations II
元素排列，输入有重复，输出不能重复
如上一题所说，一个数组去重。
比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就不应该让后面的2使用。
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
int[] visited = new int[nums.length];
List<Integer> list = new ArrayList<>();
dfs(result, list, nums, visited);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> list,
int[] nums, int[] visited) {
if (list.size() == nums.length) result.add(new ArrayList<Integer>(list));
for (int i = 0; i < nums.length; ++i) {
if (visited[i] == 1 || i != 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;
list.add(nums[i]);
visited[i] = 1;
dfs(result, list, nums, visited);
visited[i] = 0;
list.remove(list.size() - 1);
}
}
}