来Offer习题讲解专题| Subsets I 的多种解法
作者介绍：汤老师
来Offer(www.laioffer.com)金牌算法讲师。清华大学计算机系信息学竞赛保送生，美国哥伦比亚大学计算机系软件系统实验室博士生，曾在 OSDI、CACM 等操作系统领域最顶级学术会议和期刊上发表多篇论文。曾参与 Chrome 和 Google Cloud Platform 的研发工作。
Subsets, Permutations, Combinations 等DFS问题是在CS求职面试准备中非常重要的一部分，也是相对不太好透彻理解的内容。
在这里，我们在这里帮助大家给Subsets的两个经典问题做一下总结。
题目：All Subsets
Given a set of distinct integers, nums, return all possible subsets.
* Note: The solution set must not contain duplicate subsets.
* 我假设给的input nums[] 都是已经sort好的
For example,
If nums = [1,2,3], a solution is:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]
解法一、
pure recursion (bottom up)
由要解决的problem的定义出发，尝试划分成相同problem的子问题，并且利用子问题的结果来解决原来的问题，而最关键的点有两处：base case和induction rule。
base case代表的是最小号的不可分的问题，induction rule表示的是如何利用子问题的结果。
比如，我们要找 “abc” 的所有subsets，我们可以尝试先划分子问题找到induction rule：先找到“bc”组成的所有subsets {“”, “b”, “c”, “bc”}，由“abc”组成的所有subsets包含两类：1）包含“a”的subsets 和2）不包含“a”的subsets。
我们可以看到2）就是子问题“bc”的结果，而1）可以由2）的每个subset加上元素“a”来组成，依次类推。
而另一个关键点base case：最小的不可分割子问题，也就是“”的所有的subsets，自然只包含一个元素“”。
针对原来的问题，将递归的过程从下往上表现出来如下所示，当递归深度是nums.length时，
这个解法利用的是下一层recursion的结果来生成这一层的结果。
Driven Function: subsets(nums, 0);
private List<List<Integer>> subsets(int[] nums, int level) {
if (level == nums.length) {
List<Integer> emptyList = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
res.add(emptyList);
return res;
}
List<List<Integer>> lastRes = subsets(nums, level + 1);
List<List<Integer>> newRes = new ArrayList<>();
for (List<Integer> list : lastRes) {
List<Integer> newList = new ArrayList<>(list);
newList.add(nums[level]);
newRes.add(newList);
}
lastRes.addAll(newRes);
return lastRes;
}
优点: 思路简单
缺点:在不需要返回所有的结果的时候比较浪费空间，因为当前层recursion必须要知道下一层的全部结果
优化：
计算机在进行递归的时候会有额外的栈上的空间开销，当递归层数很深的时候回有可能stackoverflow，这是一个我们需要注意和重视的情况。
从上面的解法不难看出，我们可以比较容易的将它转化成Iterative的解法，从最小号的问题开始解决，利用相同的induction rule，这也是Dynamic Programming解法最根本的来源。
private List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
// base case: empty subset.
subsets.add(new ArrayList<Integer>());
for (int level = 0; level < nums.length; i++) {
int size = subsets.size();
for (int j = 0; j < size; j++) {
List<Integer> set = new ArrayList<>(subsets.get(j));
set.add(nums[level]);
subsets.add(set);
}
}
return subsets;
}
解法二、
DFS (top down)
根据来Offer孙老师的传授的要诀，用DFS基本方法解决问题时要明确两点:
- 每一层代表什么含义
搜索到当前层时所有可能的解(孙老师授课时对这个问题描述得更深刻，我没有完全理解)
2. 每层有多少个状态需要尝试
对于subsets有两个状态：加 或 不加 当前元素
代码比解法一简单很多:
Driven Function: subsets(nums, 0, new ArrayList(), res);
private void subsets(int[] nums, int level, List<Integer> curr, List<List<Integer>> res) {
// base case
if (level == nums.length) {
res.add(new ArrayList(curr));
return;
}
// case 1: add nums[level]
curr.add(nums[level]);
subsets(nums, level + 1, curr, res);
curr.remove(curr.size() — 1);
// case 2: do not add nums[level]
subsets(nums, level + 1, curr, res);
}
解法3、
对解法二树结构的不同看法
在得到DFS Recursion tree之后，我每次都是从leaf node取值。那么从树结构的中间取值可不可以？答案是可以的。
观察发现，每次都取左节点的值(包括root)，可以得到同样的结果。或者换一种角度看，因为所有的右leaf节点都可以有多个父节点与之对应，而与之对应的父节点肯定不是leaf节点。
再观察发现这些多个节点中只有一个左节点。并且，除了左leaf节点外，其余的左节点都有恰好对应一个右leaf节点。
需要多引入一个 boolean on Left 的变量来判断。这里并不能完全省略所有的右节点，因为右节点帮助我们再生成下一层的左节点。
Driven Function: subsets(nums, 0, new ArrayList(), true, res);
private void subsets(int[] nums, int level, List<Integer> curr, boolean onLeft, List<List<Integer>> res) {
// get value on left node
if (onLeft) {
res.add(new ArrayList(curr));
}
if (level == nums.length) {
return;
}
// case 1: add nums[level]
curr.add(nums[level]);
subsets(nums, level + 1, curr, true, res);
curr.remove(curr.size() — 1);
// case 2: not add nums[level]
subsets(nums, level + 1, curr, false, res);
}
解法四、
另一种DFS
这也是另一种常见的DFS思路，依然根据孙老师传授的要诀来解释这种思路:
1. 每一层代表什么含义
长度相等的所有可能性
2. 每层有多少个状态需要尝试
每一层新增的状态根据上一层来决定，如果上一层打印到了nums[st], 则这一层新增的状态是从 st + 1 到 nums.length — 1
划重点!
这个思路用到的是另外一种构建subset的方法：“每个size为k的subset都是由一个size为k-1的subset加上一个元素得到的”。
而我们在构建subset的过程当中要避免出现重复，比如：
“123”， “132”， “213”，“231”，“312”，“321”这几个都是相同的subset，我们只应该让它在我们的构建方法中出现一次，否则会有重复。
常见的Intuition是“如果我们在构建subset的过程中保持一定的顺序，那么上述这些可能出现的subset只会出现其中的唯一一个！”，那么我们可以选用的方法是，在构建subset的过程中，每次新添加的元素保持递增的顺序，这样“132”，“213”等等都不会出现在我们的结果里面，当我们已经有了一个size为1的subset “2”，我们是不会再把“21”构建出来的，下一次新添加的元素只能是比2大的所有选择。
Driven Function: subsets(nums, 0, new LinkedList(), res);
private void subsets(int[] nums, int smallestCandidate, List<Integer> curr, List<List<Integer>> res) {
res.add(new ArrayList(curr));
// 注意这里smallestCandidate这个变量的定义，它代表的是新添的元素最小的可能。
for (int i = smallestCandidate; i < nums.length; i++) {
curr.add(nums[i]);
subsets(nums, i + 1, curr, res);
curr.remove(curr.size() — 1);
}
}
E/N/D
关于来Offer：
来Offer是硅谷最具实力的高科技在线教育和职业培训机构，通过提供高水平的IT培训课程和就业指导，帮助学员进军硅谷一二线科技公司。自2013年以来，来Offer已将3000+名中国工程师送入Facebook, Google等硅谷一线公司。
点此了解来Offer课程详情：
