解1：[LC39] 组合总和
题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个数字可以无限制重复被选取 。至少一个数字的被选数量不同，则两种组合是不同的。
注意：对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 ：
输入：candidates = [2,3,6,7], target = 7 输出：[ [2,2,3],[7] ] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
解题思路：回溯
遍历所有可能的列表并判断当前列表是否符合题目的要求，回溯遍历过程中使用剪枝
由于可以重复选取，因此当选择当前位置元素后，dfs 的起始位置依旧为当前位置
复杂度分析
时间复杂度：
- 在这题中，我们很难给出一个比较紧的上界，我们知道 是一个比较松的上界，即在这份代码中，  个**位置**每次考虑**选**或者**不选**，那么  种组合都会被枚举到，而每种情况又需要  的时间将其放入答案中，因此我们将  二者相乘。如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 进行剪枝，所以实际运行情况是**远远小于**这个上界的。，即可估算出一个宽松的时间复杂度上界。
空间复杂度：
。
- 除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归  层。
我的代码
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
// 排序是剪枝的前提
Arrays.sort(candidates);
dfs(candidates, 0, len, target);
return res;
}
private void dfs(int[] candidates, int begin, int len, int target) {
// 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 重点理解这里剪枝，前提是候选数组已经有序，
if (target - candidates[i] < 0) {
break;
}
path.addLast(candidates[i]);
dfs(candidates, i, len, target - candidates[i]); // 【重复使用】
path.pollLast();
}
}
}
解题思路：完全背包
转换为完全背包问题：有 n 种不同重量的物品(candidates)，每种物品的使用次数不限，问有多少种组合方式可以恰好装满限重为 target 的背包。
class Solution(object):
def combinationSum(self, candidates, target):
dp = [[[]] if j == 0 else [] for j in range(target + 1)]
for candidate in candidates:
for j in range(candidate, target + 1):
dp[j] += [res + [candidate] for res in dp[j - candidate]]
return dp[-1]
解2：[LC40] 组合总和 II
🚩 传送门：力扣题目
题目
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
注意：candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
示例 :
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6],[1,2,5],[1,7],[2,6] ]
解题思路：回溯
若按照顺序排列：对于每个位置的数只有两种可能性，要么取，要么不取。对于 
个数的 candidates 一共有 
种组合情形。遍历出所有的组合然后判断当前组合是否合法即是否等于 target 。回溯遍历过程中使用剪枝
由于不可以重复选取，因此当选择当前位置元素后，dfs 的起始位置为当前位置的下一个位置
复杂度分析
时间复杂度：
- 在这题中，我们很难给出一个比较紧的上界，我们知道 是一个比较松的上界，即在这份代码中，  个**位置**每次考虑**选**或者**不选**，那么  种组合都会被枚举到，而每种情况又需要  的时间将其放入答案中，因此我们将  二者相乘。如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 进行剪枝，所以实际运行情况是**远远小于**这个上界的。，即可估算出一个宽松的时间复杂度上界。
空间复杂度：
。
- 除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归  层。
我的代码
public class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
// 关键步骤
Arrays.sort(candidates);
dfs(candidates, len, 0, target);
return res;
}
// len 长度、begin 起点下标、target 目标值、path 临时结果集、res 结果集
private void dfs(int[] candidates, int len, int begin, int target) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 大剪枝：当前最小的都无法满足,后面更大更无法满足 break
if (target - candidates[i] < 0) {
break;
}
// 小剪枝：重复值,跳过 continue
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
// 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
dfs(candidates, len, i + 1, target - candidates[i]); // 【不重复使用】
path.pollLast();
}
}
}
解题思路：01-背包
问题转化为 01背包 求解：
有 n 个物品，每个物品的重量在 **candidates** 数组中， 背包容量为 target ，求有多少种方案可以恰好装满背包（其中每个物品限用一次）
class Solution(object):
def combinationSum2(self, candidates, target):
dp = [[[]] if j == 0 else [] for j in range(target + 1)]
for candidate in sorted(candidates):
for j in range(target, candidate - 1, -1):
dp[j].extend(res + [candidate] for res in dp[j - candidate] if (res + [candidate]) not in dp[j])
return dp[-1]
解3：[LC216] 组合总和 III
题目
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 [ 1 - 9 ] 的正整数，并且每种组合中数不重复。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
解题思路：回溯
遍历所有可能的列表并判断当前列表是否符合题目的要求，回溯遍历过程中使用剪枝
由于可以重复选取，因此当选择当前位置元素后，dfs 的起始位置依旧为当前位置
剪枝条件：
i<10，值属于 [ 1 , 9 ]- 区间 (n - k + 1,n] 不可能构造出一个长度为 k 的序列
**sum+i<=n**，越往后值越大，当前数不合适，后面更不适合
复杂度分析
时间复杂度：
，其中 
为长度 。
空间复杂度：
，即递归使用栈空间的空间代价和临时数组 temp 的空间代价。
栈空间需要递归 **n** 层，开销很大
我的代码
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int sum=0;
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(1, n, k);
return res;
}
private void dfs(int start, int end, int k) {
if (k == 0) {
if(sum==end)
res.add(new ArrayList<>(path));
return;
}
// 剪枝:三种剪枝方式,【i<10】提升效果显著
for (int i = start; i<10 && i <= end - k + 1 && sum + i <= end; i++) {
path.add(i);
sum+=i;
dfs(i + 1, end, k - 1);
path.remove(path.size() - 1);
sum-=i;
}
}
}
解4：[LC377] 组合总和 IV
题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
请注意，顺序不同的序列被视作不同的组合。题目数据保证答案符合
32位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3 输出：0
解题思路：动态规划
👉 定义：
表示选取的元素之和等于 
的方案数，目标是求 
。
边界是 _dp_[0]=1。只有当不选取任何元素时，元素之和才为 0，因此只有 1 种组合。
我们现状考虑状态转移方程中的一种情形：对于值为 
，考虑组合结尾的元素值为 
时，如果存在一种组合之和等于 
，则在该组合中增加一个值为 
的数，即可得到一种和等于 
的组合。因此对于求解 
的总组合数，需要遍历 
，对于其中的每一种元素值，都让其作为结尾，并计算组合数，最终求和更新数组 
。
🚩详情参考：兑换硬币 II （一个内循环，一个外循环）
边界条件： 
，只有当不选取任何元素时，元素之和才为 0，因此只有 1 种组合。
🤣综上所述，我们不难发现，状态转移方程：
时间复杂度：
，其中 
为数组 
的长度，其中 
是总目标和。
空间复杂度：
，其中 
是总金额 。需要创建长度为 
的数组 
。
🚩我的代码
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
进阶问题：如果给定的数组中含有负数，则会导致出现无限长度的排列。
例如，假设数组 nums 中含有正整数 a 和负整数 -b（其中 a>0,-b<0），则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，在该排列的后面添加 b 个 a 和 a 个 −b 之后，得到的新排列的元素之和仍然等于 target，而且还可以继续添加，可以构造出无限长度的排列。
如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。
若有收获，就点个赞吧
0 人点赞
