分享一个subset及其衍生题的模板。这类题，你只需要一个模板

dontbeevil

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

我们先来看一个经典的78. subset： Given a set of distinct integers, nums, return all possible subsets (the power set).

对于这个题，我们要生成所有的subset，那么我们需要考虑怎么取到所有的可能性，其实思路想明白了很简单：对于每个元素，我们有取和不取两种可能性。借助一个辅助DFS函数，去实现这个取和不取的两种情况，我们就能枚举所有的子集了。代码如下：

class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
dfs(nums, res, 0, new ArrayList<>());
return res;
}
private void dfs(int[] nums, List<List<Integer>> res, int pos, List<Integer> set) {
if (pos == nums.length) {
res.add(new ArrayList<>(set));
return;
}
// pick this element
set.add(nums[pos]);
dfs(nums, res, pos + 1, set);
set.remove(set.size() - 1);
// not pick this element
dfs(nums, res, pos + 1, set);
}
}

复制代码

接下来我们看followup, 如果备选元素有重复，怎么生成所有的子集。其实思路也很简单，我们需要判重。所有在上面一题的基础上，加一段判重就可以。其他地方不改变。代码如下：

class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
dfs(nums, res, 0, new ArrayList<>());
return res;
}
private void dfs(int[] nums, List<List<Integer>> res, int pos, List<Integer> set) {
if (pos == nums.length) {
res.add(new ArrayList<>(set));
return;
}
// pick this element
set.add(nums[pos]);
dfs(nums, res, pos + 1, set);
set.remove(set.size() - 1);
// before the not pick element process, we need to get rid of the duplications, if the current element is the same as the next one, just advance the moving pointer
while (pos + 1 < nums.length && nums[pos + 1] == nums[pos]) {
pos++;
}
// not pick this element
dfs(nums, res, pos + 1, set);
}
}

复制代码

接下来我们来看39. Combination Sum。这个题和subset就是一个题，无非现在我们需要知道subset的和，判断和是不是target就行。如果是，表明找到这个combination。大部分的代码还是和subset一样。代码如下：

class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
dfs(candidates, res, target, 0, new ArrayList<>());
return res;
}
private void dfs(int[] cands, List<List<Integer>> res, int T, int pos, List<Integer> comb) {
// if we found the target combination sum
if (T == 0) {
res.add(new ArrayList<>(comb));
return;
}
// if we undershoot the sum
if (T < 0) {
return;
}
// if we used all the elements
if (pos >= cands.length) {
return;
}
// use the current element to make the combination
comb.add(cands[pos]);
dfs(cands, res, T - cands[pos], pos, comb);
comb.remove(comb.size() - 1);
// skip the current element to make the combination by moving the index to next element and keep the T
dfs(cands, res, T, pos + 1, comb);
}
}

复制代码

40. Combination Sum II。这个题和subset II是一样的思路，我们需要判重，那么在上一题的基础上，加上判重逻辑就解决问题。代码如下

class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
dfs(candidates, target, res, new ArrayList<>(), 0);
return res;
}
private void dfs(int[] nums, int T, List<List<Integer>> res, List<Integer> comb, int pos) {
if (T < 0) return;
if (T == 0) {
res.add(new ArrayList<>(comb));
return;
}
if (pos >= nums.length) return;
comb.add(nums[pos]);
dfs(nums, T - nums[pos], res, comb, pos + 1);
comb.remove(comb.size() - 1);
// deduplicate, the other parts are just like Q.39.
while (pos + 1 < nums.length && nums[pos + 1] == nums[pos]) { // this place is error prone. WHile instead of if
pos++;
}
//if (pos + 1 < nums.length && nums[pos + 1] == nums[pos]) continue;
dfs(nums, T, res, comb, pos + 1);
}
}

复制代码

77. Combinations. 这个题还是沿用一样的subset的模板。无非现在是取值的范围变化了而已。其他的逻辑还是一样的。代码如下：

class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
dfs(1, n, k, res, new ArrayList<>());
return res;
}
private void dfs(int s, int e, int count, List<List<Integer>> res, List<Integer> comb) {
if (comb.size() == count) {
res.add(new ArrayList<>(comb));
return;
}
if (s >= e + 1) {
return;
}
comb.add(s);
dfs(s + 1, e, count, res, comb);
comb.remove(comb.size() - 1);
dfs(s + 1, e, count, res, comb);
}
}

复制代码

216. Combination Sum III。这个题还是一样的模板题。根据题意改一下base case就行。代码如下：

class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
dfs(k, n, res, 1, new ArrayList<>());
return res;
}
private void dfs(int k, int n, List<List<Integer>> res, int s, List<Integer> comb) {
if (n < 0) {
return;
}
if (n == 0 && comb.size() == k) {
res.add(new ArrayList<>(comb));
return;
}
if (s >= 10) {
return;
}
comb.add(s);
dfs(k, n - s, res, s + 1, comb);
comb.remove(comb.size() - 1);
dfs(k, n, res, s + 1, comb);
}
}

复制代码

总结：通过subset每个元素取还是不取，我们就能枚举一个数组里面所以的子集。然后根据题意去构造最终的目标。这六个题就迎刃而解了。而且这样写起来，出错的可能性更低。

Happy coding。新手上路，发点有营养的帖子，希望各位看官走过路过加点米，好看面经，刷题上岸。先谢过了。

tianjiayangmike

感谢楼主分享，补充一个permutation的题，好像是131 palindrome permutation。然后中国面试有一个特别爱问的是字符串的全排列。俩题基本和楼主的题是一个模子里的

我的个人感觉是 subset， permutation的本质区别在于画完递归树，subset是路径上节点都会往里加，然后permutation只会去加叶子节点。然后基于此，有一些比如去重/排序等小trick来帮助剪枝，还有一些小小的变形题，可能会对加入res有一些额外的要求。

好久没做这块儿的题里，纯凭记忆打的，不一定对

ggaimm2002

楼主总结的很好

[高频题] 分享一个subset及其衍生题的模板。这类题，你只需要一个模板

注册一亩三分地论坛，查看更多干货！

评分

本帖被以下淘专辑推荐:

评分

浏览过的版块