回溯算法解组合总和问题（Python，Java，C语言）
题目
给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入:candidates = [2,3,5], target = 8
输出:[[2,2,2,2],[2,3,3],[3,5]]
Python解法（回溯）
代码示例
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] combine = [] def dfs(idx:int, remain:int): if idx == len(candidates): return if remain == 0: ans.append(combine.copy()) return if remain - candidates[idx] >= 0: combine.append(candidates[idx]) dfs(idx, remain - candidates[idx]) combine.pop() dfs(idx+1, remain) dfs(0, target) return ans解释
此题主要是函数部分。
1，先列出数组遍历完和找到正确的一种情况进行保存
注意：保存要用copy，否则会被回溯消失
# 遍历完所有数字，返回 if idx == len(candidates): return # 找到合法组合，加入答案 if remain == 0: ans.append(combine.copy()) return2，理解寻找过程中的两个情况（改变索引或者改变临时变量值）
# 选择1：选当前数字（可重复选） if remain - candidates[idx] >= 0: combine.append(candidates[idx]) dfs(idx, remain - candidates[idx]) # 索引不变，可重复选 combine.pop() # 回溯，撤销选择 # 选择2：不选当前数字，直接下一个 dfs(idx + 1, remain)图片解释
用的例子：candidates = [2,3,6,7]，target = 7
Java解法
代码示例
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>(); List<Integer> combine = new ArrayList<>(); dfs(candidates, target, ans, combine, 0); return ans; } private void dfs(int[] candidates, int remain, List<List<Integer>> ans, List<Integer> combine, int idx) { // 遍历完所有数字，返回 if (idx == candidates.length) { return; } // 找到合法组合，加入答案 if (remain == 0) { ans.add(new ArrayList<>(combine)); return; } // ================== 选择一：先选当前数字（和你Python完全一致）================== if (remain - candidates[idx] >= 0) { combine.add(candidates[idx]); dfs(candidates, remain - candidates[idx], ans, combine, idx); combine.remove(combine.size() - 1); // 回溯 } // ================== 选择二：再跳过当前数字（和你Python完全一致）================== dfs(candidates, remain, ans, combine, idx + 1); } }C语言解法
代码示例
// 用于存储结果 int** ans; int* ansColSize; int ansSize; // 用于存储当前组合 int* path; int pathSize; void dfs(int* candidates, int candidatesSize, int target, int idx) { // 遍历完所有数字，返回 if (idx == candidatesSize) { return; } // 找到合法组合，保存结果 if (target == 0) { // 申请空间保存当前组合 int* tmp = (int*)malloc(sizeof(int) * pathSize); memcpy(tmp, path, sizeof(int) * pathSize); ans[ansSize] = tmp; ansColSize[ansSize] = pathSize; ansSize++; return; } // ================== 选择一：先选当前数字 ================== if (target - candidates[idx] >= 0) { path[pathSize++] = candidates[idx]; // 加入 dfs(candidates, candidatesSize, target - candidates[idx], idx); // idx不变，可重复选 pathSize--; // 回溯，撤销 } // ================== 选择二：再跳过当前数字 ================== dfs(candidates, candidatesSize, target, idx + 1); } // LeetCode 标准接口 int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { ansSize = 0; pathSize = 0; // 预估最大空间（足够大） ans = (int**)malloc(sizeof(int*) * 1001); ansColSize = (int*)malloc(sizeof(int) * 1001); path = (int*)malloc(sizeof(int) * 1001); dfs(candidates, candidatesSize, target, 0); *returnSize = ansSize; *returnColumnSizes = ansColSize; return ans; }