LeetCode-216. 组合总和 III
2020-09-11
问题地址
LeetCode216. 组合总和 III
问题描述
规则
- 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 – 9 的正整数，并且每种组合中不存在重复的数字。
说明
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例
- 示例一：
输入: k = 3, n = 7
输出: [[1,2,4]]
- 示例二：
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解析
解题思路
- 今天的题目和前两天的每日一题类似，都可可以尝试用「搜索回溯」的方法来解决。
-
相似题目：
数据操作分析
- 使用递归；
- 递归终止条件：
- 当前答案集中元素数量>k
- 当前n<0
- 当前答案集中元素个数==k 且 n==0
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
/**
* LeetCode0216
*/
public class LeetCode0216_CombinationSumiii {
/**
* @param k k个数的组合
* @param n 和为n
* @return
*/
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
Map<List<Integer>, Integer> map = new HashMap<>();
List<Integer> tmp = new ArrayList<>();
int start = 1;
dfs(k, n, ans, tmp, start);
return ans;
}
private void dfs(int k, int n, List<List<Integer>> ans, List<Integer> tmp, int start) {
if (n < 0 || n > 45 || k < 1 || k > 9) return;
//找到符合要求的组合
if (tmp.size() == k && n == 0) {
ans.add(new ArrayList<>(tmp));
return;
}
for (int i = start; i <= 9; i++) {
tmp.add(i);
dfs(k, n - i, ans, tmp, i + 1);
tmp.remove(tmp.size() - 1);//最后添加的先删除
}
}
}
官方解法
方法一：二进制（子集）枚举
思路：
- 「组合中只允许含有 1−9 的正整数，并且每种组合中不存在重复的数字」意味着这个组合中最多包含 9 个数字。我们可以把原问题转化成集合 S ={1,2,3,4,5,6,7,8,9 }，我们要找出 SS 的当中满足如下条件的子集：
- 大小为 k
- 集合中元素的和为 n
- 因此我们可以用子集枚举的方法来做这道题。即原序列中有 9 个数，每个数都有两种状态，「被选择到子集中」和「不被选择到子集中」，所以状态的总数为 2^9。我们用一个 9 位二进制数 \rm mask 来记录当前所有位置的状态，从第到高第 i 位为 0 表示 i 不被选择到子集中，为 1 表示 i 被选择到子集中。当我们按顺序枚举 [0, 2^9 – 1] 中的所有整数的时候，就可以不重不漏地把每个状态枚举到，对于一个状态 \rm mask，我们可以用位运算的方法得到对应的子集序列，然后再判断是否满足上面的两个条件，如果满足，就记录答案。
- 如何通过位运算来得到 \rm mask 各个位置的信息？对于第 i 个位置我们可以判断 (1 << i ) & mask 是否为 0，如果不为 0 则说明 i 在子集当中。当然，这里要注意的是，一个 9 位二进制数 i 的范围是 [0, 8]，而可选择的数字是 [1, 9]，所以我们需要做一个映射，最简单的办法就是当我们知道 i 位置不为 0 的时候将 i + 1 加入子集。
- 当然，子集枚举也可以用递归实现。在「官方题解 – 77. 组合」的方法一中提及了子集枚举递归实现的基本框架，感兴趣的同学可以参考。
复杂度分析
- 时间复杂度 O(M×2^M)，其中 M 为集合的大小，本题中 M 固定为 9。一共有 2^M 个状态，每个状态需要 O(M + k) = O(M) 的判断（k \leq M），故时间复杂度为 O(M \times 2^M)。
- 空间复杂度：O(M)。即 \rm temp 的空间代价。
编码实现
class Solution {
List<Integer> temp = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum3(int k, int n) {
for (int mask = 0; mask < (1 << 9); ++mask) {
if (check(mask, k, n)) {
ans.add(new ArrayList<Integer>(temp));
}
}
return ans;
}
public boolean check(int mask, int k, int n) {
temp.clear();
for (int i = 0; i < 9; ++i) {
if (((1 << i) & mask) != 0) {
temp.add(i + 1);
}
}
if (temp.size() != k) {
return false;
}
int sum = 0;
for (int num : temp) {
sum += num;
}
return sum == n;
}
}
方法一：组合枚举
思路：
- 我们可以换一个思路：我们需要在 9 个数中选择 k 个数，让它们的和为 n。
- 这样问题就变成了一个组合枚举问题。组合枚举有两种处理方法——递归法和字典序法，在「官方题解 – 77. 组合」中有详细的说明。
- 这里我们要做的是做一个「在 9 个数中选择 k 个数」的组合枚举，对于枚举到的所有组合，判断这个组合内元素之和是否为 n。
复杂度分析
- 时间复杂度 O( M \choose k ×k)，其中 M 为集合的大小，本题中 M 固定为 9。一共有 M \choose k 个组合，每次判断需要的时间代价是 O(k)。
- 空间复杂度：O(M)。temp 数组的空间代价是 O(k)，递归栈空间的代价是 O(M)，故空间复杂度为 O(M + k) = O(M)。
编码实现
class Solution {
List<Integer> temp = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(1, 9, k, n);
return ans;
}
public void dfs(int cur, int n, int k, int sum) {
if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
return;
}
if (temp.size() == k) {
int tempSum = 0;
for (int num : temp) {
tempSum += num;
}
if (tempSum == sum) {
ans.add(new ArrayList<Integer>(temp));
return;
}
}
temp.add(cur);
dfs(cur + 1, n, k, sum);
temp.remove(temp.size() - 1);
dfs(cur + 1, n, k, sum);
}
}
精彩评论
跳转地址1：「手画图解」216. 组合总和 III
一句话解题
相似题目
- 因为最近每日一题的重叠度太高了，我再把回溯拿出来讲一遍，就很累，我贴出前两天写的题解。
编码实现
const combinationSum3 = (k, n) => {
const res = [];
const dfs = (start, temp, sum) => {
if (temp.length == k) { // You've selected k numbers. End recursion
if (sum == n) { // The sum of numbers in a combination equals n
res.push(temp.slice()); // Add its copy to the solution set
}
return;
}
for (let i = start; i <= 9; i++) { // Enumerate the options
temp.push(i); // Make a choice
dfs(i + 1, temp, sum + i); // Explore
temp.pop(); // Undo the choice
}
};
dfs(1, [], 0); // press the search button
return res;
};