在这里，我们再复习一下 LeetCode 第 77 题。剪枝主要的出发点就在于，我们可以提前做好判断，减少不必要的比较开销。
LeetCode 第 77 题：组合-2
添加打印输出，帮助理清程序执行流程。
Java 代码：我们以 ，
为例运行我们的代码：
public static void main(String[] args) {
Solution solution = new Solution();
List<List<Integer>> combine = solution.combine(5, 3);
System.out.println(combine);
}
可以发现，其中绿色的部分，是不能产生结果的分支，但是我们的代码确实又执行到了这部分。我们可以在 generateCombinations() 函数中添加如下输出：
private void generateCombinations(int n, int k, int start, List<Integer> pre) {
if (pre.size() == k) { // pre.size() == k
result.add(new ArrayList<>(pre));
return;
}
for (int i = start; i <= n; i++) {
pre.add(i);
// 添加的打印语句1
System.out.println(pre + " new start：" + (i + 1));
generateCombinations(n, k, i + 1, pre);
pre.remove(pre.size() - 1);
// 添加的打印语句2
System.out.println(pre);
}
}
此时的打印语句为：
[1] new start：2
[1, 2] new start：3
[1, 2, 3] new start：4
[1, 2]
[1, 2, 4] new start：5
[1, 2]
[1, 2, 5] new start：6
[1, 2]
[1]
[1, 3] new start：4
[1, 3, 4] new start：5
[1, 3]
[1, 3, 5] new start：6
[1, 3]
[1]
[1, 4] new start：5
[1, 4, 5] new start：6
[1, 4]
[1]
[1, 5] new start：6
[1]
[]
[2] new start：3
[2, 3] new start：4
[2, 3, 4] new start：5
[2, 3]
[2, 3, 5] new start：6
[2, 3]
[2]
[2, 4] new start：5
[2, 4, 5] new start：6
[2, 4]
[2]
[2, 5] new start：6
[2]
[]
[3] new start：4
[3, 4] new start：5
[3, 4, 5] new start：6
[3, 4]
[3]
[3, 5] new start：6
[3]
[]
[4] new start：5
[4, 5] new start：6
[4]
[]
[5] new start：6
[]
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
上面的代码中，我们发现：其实如果 pre 已经选择到 [1,4,5] 或者 [2,4,5] 或者 [3,4,5] ，此时后续的一些代码就没有必要执行了，因此继续走也不能发现新的满足题意的元素。所以干了类似与下面事情，其实有很多步骤是多余的：选择了 [1,4,5] 以后， 5 跳出 [1,4,5] 成为 [1,4] , 4 跳出 [1,4] 成为 4 ，然后 5 进来，成为 [1,5]，在进来发现 for 循环都进不了（因为没有可选的元素），然后 5 又跳出，接着 1 跳出。
发现多余操作：那么我们如何发现多余的步骤呢，其实也是有规律可寻的，就在 for 循环中：
for (int i = start; i <= n; i++) {
pre.add(i);
generateCombinations(n, k, i + 1, pre);
pre.remove(pre.size() - 1);
}
这个函数干的事情，是从 这个区间里（注意，左右都是闭区间），找到
k-pre.zize() 个元素。 i <= n 不是每一次都要走完的， i 有一个上限。
寻找规律：我们再看图，可以发现一些边界情况，帮助我们发下规律:
当选定了一个元素，即 pre.size() == 1 的时候，接下来要选择 2 个元素， i 最大的值是 4 ，因为从 5 开始选择，就无解了；
当选定了两个元素，即 pre.size() == 2 的时候，接下来要选择 1 个元素， i 最大的值是 5 ，因为从 6 开始选择，就无解了。
再如：如果 n = 6 ，k = 4，
pre.size() == 1 的时候，接下来要选择 3 个元素， i 最大的值是 4，最后一个被选的是 [4,5,6]；
pre.size() == 2 的时候，接下来要选择 2 个元素， i 最大的值是 5，最后一个被选的是 [5,6]；
pre.size() == 3 的时候，接下来要选择 1 个元素， i 最大的值是 6，最后一个被选的是 [6]；
再如：如果 n = 15 ，k = 4，
pre.size() == 1 的时候，接下来要选择 3 个元素， i 最大的值是 13，最后一个被选的是 [13,14,15]；
pre.size() == 2 的时候，接下来要选择 2 个元素， i 最大的值是 14，最后一个被选的是 [14,15]；
pre.size() == 3 的时候，接下来要选择 1 个元素， i 最大的值是 15，最后一个被选的是 [15]；
多写几遍（发现 max(i) 是我们倒着写出来），我么就可以发现 max(i) 与 接下来要选择的元素貌似有一点关系，很容易知道：
max(i) + 接下来要选择的元素个数 - 1 = n，其中， 接下来要选择的元素个数 = k - pre.size()，整理得到：
。
所以，我们的剪枝过程就可以体现在，把 i <= n 改成 i <= n - (k - pre.size()) + 1 ：
for (int i = start; i <= n - (k - pre.size()) + 1; i++) {
pre.add(i);
generateCombinations(n, k, i + 1, pre);
pre.remove(pre.size() - 1);
}
// p 可以声明成一个栈
// i 的极限值满足： n - i + 1 = (k-pre.size())。
// n - i + 1 是闭区间 [i,n] 的长度。
// k - pre.size() 是剩下还要寻找的数的个数。
private void findCombinations(int n, int k, int index, Stack<Integer> p) {
if (p.size() == k) {
result.add(new ArrayList<>(p));
return;
}
for (int i = index; i <= n - (k - p.size()) + 1; i++) {
p.push(i);
findCombinations(n, k, i + 1, p);
p.pop();
}
}
观察结果：此时打印输出语句就会少很多。
[1] new start：2
[1, 2] new start：3
[1, 2, 3] new start：4
[1, 2]
[1, 2, 4] new start：5
[1, 2]
[1, 2, 5] new start：6
[1, 2]
[1]
[1, 3] new start：4
[1, 3, 4] new start：5
[1, 3]
[1, 3, 5] new start：6
[1, 3]
[1]
[1, 4] new start：5
[1, 4, 5] new start：6
[1, 4]
[1]
[]
[2] new start：3
[2, 3] new start：4
[2, 3, 4] new start：5
[2, 3]
[2, 3, 5] new start：6
[2, 3]
[2]
[2, 4] new start：5
[2, 4, 5] new start：6
[2, 4]
[2]
[]
[3] new start：4
[3, 4] new start：5
[3, 4, 5] new start：6
[3, 4]
[3]
[]
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
练习1：LeetCode 第 39 题：组合总和
传送门：英文网址：39. Combination Sum ，中文网址：39. 组合总和 。
给定一个无重复元素的数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字可以无限制重复被选取。说明：
- 所有数字（包括
target）都是正整数。- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]示例 2:
输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
求解关键：注意分析题意，找到可以减少判断的条件：
1、这道题猛地一看好像跟前面的问题搭不上关系，因为题目中说“candidates 中的数字可以无限制重复被选取”；
2、但其实仔细想想就会发现，我们每次取数字的时候，还从原点开始取就行了呀，是不是很酷；
3、为了达到提前判断循环结束的效果，我们可以先对数组排个序，如果起点数字比剩下的和还要大，后面的循环就没有必要进行下去了。此时，我们在 for 循环里加判断，尽量减少了系统栈的调用深度。
Java 实现：没有做剪枝优化的版本。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// https://leetcode-cn.com/problems/combination-sum/description/
public class Solution {
private List<List<Integer>> res = new ArrayList<>();
private int[] candidates;
private int len;
// residue 定义为剩余，这个剩余一开始等于 target，在递归中，它的值会越来越小
// 因为题目中说了"所有数字（包括 target）都是正整数"。
private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
// 因为可以无限选取，所以 residue 只能小于 0 或者等于 0
if (residue < 0) {
return;
}
// 一定是剩下的那个数为 0 了，才表示我们所选的数字的和刚好等于 target
if (residue == 0) {
res.add(new ArrayList<>(pre));
return;
}
for (int i = start; i < len; i++) {
// 每个数有选择和不选择，因此尝试了一种解的可能以后要进行状态重置
pre.add(candidates[i]);
// 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
findCombinationSum(residue - candidates[i], i, pre);
pre.pop();
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
this.len = len;
this.candidates = candidates;
findCombinationSum(target, 0, new Stack<>());
return res;
}
public static void main(String[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
Solution solution = new Solution();
List<List<Integer>> combinationSum = solution.combinationSum(candidates, target);
System.out.println(combinationSum);
}
}
Java 代码：剪枝的版本。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class Solution2 {
private List<List<Integer>> res = new ArrayList<>();
private int[] candidates;
private int len;
private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
if (residue == 0) {
res.add(new ArrayList<>(pre));
return;
}
// 优化添加的代码2：在循环的时候做判断，尽量避免系统栈的深度
// residue - candidates[i] 表示下一轮的剩余，如果下一轮的剩余都小于 0 ，就没有必要进行后面的循环了
// 这一点基于原始数组是排序数组的前提，因为如果计算后面的剩余，只会越来越小
for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
pre.add(candidates[i]);
// 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
findCombinationSum(residue - candidates[i], i, pre);
pre.pop();
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
// 优化添加的代码1：先对数组排序，可以提前终止判断
Arrays.sort(candidates);
this.len = len;
this.candidates = candidates;
findCombinationSum(target, 0, new Stack<>());
return res;
}
}
练习2：LeetCode 第 40 题：组合总和 II
传送门：英文网址：40. Combination Sum II ，中文网址：40. 组合总和 II 。
给定一个数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
求解关键：找到如何在结果集中去除重复的方法。
1、与第 39 题的区别，第 39 题的数组没有重复数字，可以使用多次；第 40 题的数组有重复数字，只能使用一次，具体就体现在进行下一层递归的时候，起始的那个索引值是多少；
（2）很容易想到，应该先对给出的数组进行排序，排序的目的有两个：其一是，可以提前终止循环，其二是“在递归函数的调用中，同一深度的一个值只能使用一次”，这一处理也几乎成为了标准写法，或许刚刚开始接触的时候并不好理解，应该使用具体的例子画出图来理解，然后多做一些类似练习，理解代码为什么那样写。
C++ 写法：
LeetCode 第 40 题：组合总和 II-1
Java 写法：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
// https://leetcode-cn.com/problems/combination-sum-ii/description/
public class Solution {
private List<List<Integer>> res = new ArrayList<>();
private int[] candidates;
private int len;
// residue 表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
// residue 在递归遍历中，只会越来越小
private void findCombinationSum2(int residue, int begin, Stack<Integer> stack) {
if (residue == 0) {
res.add(new ArrayList<>(stack));
return;
}
for (int i = begin; i < len && residue - candidates[i] >= 0; i++) {
// 这一步之所以能够生效，其前提是数组一定是排好序的，这样才能保证：
// 在递归调用的统一深度（层）中，一个元素只使用一次。
// 这一步剪枝操作基于 candidates 数组是排序数组的前提下
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
stack.add(candidates[i]);
// 【关键】因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
findCombinationSum2(residue - candidates[i], i + 1, stack);
stack.pop();
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
this.len = len;
// 先将数组排序，这一步很关键
Arrays.sort(candidates);
this.candidates = candidates;
findCombinationSum2(target, 0, new Stack<>());
return res;
}
public static void main(String[] args) {
int[] candidates = {2, 5, 2, 1, 2};
int target = 5;
Solution solution = new Solution();
List<List<Integer>> combinationSum2 = solution.combinationSum2(candidates, target);
System.out.println(combinationSum2);
}
}
练习3：LeetCode 第 216 题：组合总和 III
传送门：组合总和 III。
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]]示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
要求：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有1 - 9的正整数，并且每种组合中不存在重复的数字。
Java 代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// https://leetcode-cn.com/problems/combination-sum-iii/description/
// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有1 - 9的正整数，并且每种组合中不存在重复的数字。
public class Solution {
private List<List<Integer>> res = new ArrayList<>();
private int k;
private void findCombinationSum3(int target, int depth, int start, Stack<Integer> stack) {
if (target == 0 && depth == k) {
res.add(new ArrayList<>(stack));
return;
}
// 注意：题目中要求组合中只允许含有 1 - 9 的正整数。
for (int i = start; i <= 9 && target - i >= 0; i++) {
stack.add(i);
findCombinationSum3(target - i, depth + 1, i + 1, stack);
stack.pop();
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
if (k < 0 || n < 0 || k > n) {
return res;
}
if (n > (9 * k - (k * (k - 1)) / 2)) {
return res;
}
this.k = k;
// 注意，深度应该从 0 开始，往下走一层，深度加 1 ，加到 3 为止
findCombinationSum3(n, 0, 1, new Stack<>());
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
int k = 3;
int n = 15;
List<List<Integer>> combinationSum3 = solution.combinationSum3(k, n);
System.out.println(combinationSum3);
}
}
练习4：LeetCode 第 78 题：子集
传送门：78. 子集。
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
思路：对每一位的元素，有选择和不选择两种做法。
Python 代码：
# 78. 子集
# 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
# 说明：解集不能包含重复的子集。
# 关键词：不含重复元素
# 参考资料：花花酱 https://mp.weixin.qq.com/s/AWuv4p-RQyoCW22DczfTVA
# 参考资料：花花酱 https://mp.weixin.qq.com/s/AWuv4p-RQyoCW22DczfTVA
class Solution:
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
def dfs(max_count, begin, path):
# n 表示当前全排列的个数
# cur 表示已经拿到的 path
if max_count == len(path):
# 够数了，就加到结果集中
res.append(path.copy())
return
for i in range(begin, len(nums)):
# 加进去表示考虑这个元素
path.append(nums[i])
# 注意：这里是 i
dfs(max_count, i + 1, path)
# pop() 表示不考虑这个元素
path.pop()
for i in range(len(nums) + 1):
dfs(i, 0, [])
return res
if __name__ == '__main__':
nums = [1, 2, 3]
solution = Solution()
result = solution.subsets(nums)
print(result)
Java 写法：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* https://leetcode-cn.com/problems/subsets/description/
*/
public class Solution2 {
private void findSubsets(int[] nums, int begin, int len, Stack<Integer> stack, List<List<Integer>> res) {
// 在遍历的过程中，收集
res.add(new ArrayList<>(stack));
for (int i = begin; i < len; i++) {
stack.add(nums[i]);
findSubsets(nums, i + 1, len, stack, res);
stack.pop();
}
}
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
if (len == 0) {
return res;
}
findSubsets(nums, 0, len, new Stack<>(), res);
return res;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution2 solution = new Solution2();
List<List<Integer>> subsets = solution.subsets(nums);
System.out.println(subsets);
}
}
练习5：LeetCode 第 90 题：子集 II
传送门：英文网址：90. Subsets II ，中文网址：90. 子集 II 。
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
Python 代码：
# 90. 子集 II
# 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
# 说明：解集不能包含重复的子集。
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
l = len(nums)
if l == 0:
return []
nums.sort()
res = []
def dfs(max_count, begin, path):
if max_count == len(path):
res.append(path.copy())
return
for i in range(begin, len(nums)):
# 注意：这里不要写成 i > 0
if i > begin and nums[i - 1] == nums[i]:
continue
path.append(nums[i])
dfs(max_count, i + 1, path)
path.pop()
for max_count in range(0, l + 1):
dfs(max_count, 0, [])
return res
if __name__ == '__main__':
nums = [1, 2, 2]
solution = Solution()
result = solution.subsetsWithDup(nums)
print(result)
Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
* https://leetcode-cn.com/problems/subsets-ii/description/
*/
public class Solution {
private void findSubsetsWithDup(int[] nums, int maxCount, int begin, int len,
boolean[] marked, Stack<Integer> stack,
List<List<Integer>> res) {
if (maxCount == stack.size()) {
res.add(new ArrayList<>(stack));
return;
}
for (int i = begin; i < len; i++) {
if (!marked[i]) {
// 去重都有这一步加上排序
if (i > begin && nums[i] == nums[i - 1]) {
continue;
}
marked[i] = true;
stack.add(nums[i]);
findSubsetsWithDup(nums, maxCount, i + 1, len, marked, stack, res);
stack.pop();
marked[i] = false;
}
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 排序很关键
Arrays.sort(nums);
boolean[] marked = new boolean[len];
for (int i = 0; i <= len; i++) {
findSubsetsWithDup(nums, i, 0, len, marked, new Stack<>(), res);
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 2};
List<List<Integer>> subsetsWithDup = solution.subsetsWithDup(nums);
System.out.println(subsetsWithDup);
}
}
练习6：LeetCode 第 401 题：二进制手表问题
传送门：401. 二进制手表。
二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
LeetCode 第 401 题：二进制手表问题例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
案例:
输入: n = 1 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]注意事项:
- 输出的顺序没有要求。
- 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
- 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
典型的组合问题。
Java 代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
// https://leetcode-cn.com/problems/binary-watch/description/
public class Solution {
private List<String> res = new ArrayList<>();
private int[] hourArr = {8, 4, 2, 1};
private int[] minuteArr = {32, 16, 8, 4, 2, 1};
public List<String> readBinaryWatch(int num) {
if (num > 10 || num < 0) {
return res;
}
for (int i = 0; i <= num; i++) {
// 应该定义组合
List<Integer> hourCombination = findCombination(hourArr, i);
List<Integer> minuteCombination = findCombination(minuteArr, num - i);
for (int j = 0; j < hourCombination.size(); j++) {
if (hourCombination.get(j) > 11) {
continue;
}
for (int k = 0; k < minuteCombination.size(); k++) {
if (minuteCombination.get(k) > 59) {
continue;
}
res.add(hourCombination.get(j) + ":" + (minuteCombination.get(k) < 10 ? "0" + minuteCombination.get(k) : minuteCombination.get(k)));
}
}
}
return res;
}
private List<Integer> findCombination(int[] arr, int count) {
List<Integer> res = new ArrayList<>();
findCombination(arr, count, 0, new Stack<>(), res);
return res;
}
private Integer sum(List<Integer> pre) {
int sum = 0;
for (int i = 0; i < pre.size(); i++) {
sum += pre.get(i);
}
return sum;
}
private void findCombination(int[] arr, int count, int start, Stack<Integer> pre, List<Integer> res) {
if (pre.size() == count) {
res.add(sum(pre));
return;
}
for (int i = start; i < arr.length; i++) {
pre.push(arr[i]);
findCombination(arr, count, i + 1, pre, res);
pre.pop();
}
}
public static void main(String[] args) {
// write your code here
Solution solution = new Solution();
List<String> readBinaryWatch = solution.readBinaryWatch(2);
System.out.println(readBinaryWatch);
}
}
（本节完）
