最近在牛客网上看到一网友说自己面试的时候被面试官羞辱:原因就是在面试的时候一上来就满满的压迫感,一脸不在乎,不耐烦的样子。网友说这是因为面试要看眼缘,喜欢的就是喜欢,不喜欢的就是各种刁难。 --------------下面是今天的算法题-------------- 来看下今天的算法题,这题是LeetCode的第39题:组合总和。 给你一个无重复元素的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ,并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释: 2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选, 7 = 7 。 仅有这两种组合。
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 这题让从数组中找出一些元素,让他们的和等于 target ,问有多少个这种组合,每个元素可以使用无数次,但不能有重复组合,比如[1,2]和[2,1]实际上属于一种组合。
这是一道经典的回溯算法问题,对于所有的回溯算法我们都可以把它当做一棵树来解决。对于这道题来说因为数组中没有重复的元素,为了防止出现重复的组合,当我们选择当前元素的时候,下一步就不能再选择他前面的元素,否则就会出现类似于[1,2]和[2,1]的这两种结果。我们以示例 1 为例画个图看下选择的过程。 对于这棵树每一个分支的选择都会依赖于父节点的选择,比如父节点选择了 3 ,那么子节点就只能选择 3 以及他后面的元素,不能选择他前面的,否则就会出现重复的组合。 这里只需要计算所有的从根节点到叶子节点路径上的节点和,判断这个路径上的和是否等于 target ,如果等于,说明他就是我们要找的,直接把它添加到结果集中。 这里的关键点是怎么判断是否是叶子节点,其实很简单,如果从根节点到当前节点累加的值等于或大于 target 了,就表示到了叶子节点,因为数组中的元素都是正整数,越往下累加值就会越大,所以当累加值等于或大于 target 的时候,当前节点就是叶子节点。 对于路径上的节点当往下走的时候要选择,往回走的时候要记得移除,这就是回溯算法,最后我们再来看下代码。 public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> ans = new ArrayList<>();// 返回的结果集 dfs(ans, new ArrayList<>(), candidates, target, 0); return ans; }
private void dfs(List<List<Integer>> res, List<Integer> path, int candidates[], int target, int start) { // 因为数组中的元素都是正数,所以这里当target <= 0的时候要终止 if (target <= 0) { if (target == 0) // 如果找到一组解就把他保存下来 res.add(new ArrayList<>(path)); return; } // 这里要注意,因为不能有重复的组合,所以循环的起始位置不是0, // 否则会出现类似于[1,2]和[2,1]这种重复的组合。 for (int i = start; i < candidates.length; i++) { // 递归的三步走,选择当前元素 path.add(candidates[i]); // 递归,到树的下一层,这里target要减去当前元素的值 dfs(res, path, candidates, target - candidates[i], i); // 递归往回走要撤销选择 path.remove(path.size() - 1); } }
public: vector<vector<int>> combinationSum(vector<int> &candidates, int target) { vector<vector<int>> ans;// 返回的结果集 vector<int> path; dfs(ans, path, candidates, target, 0); return ans; }
void dfs(vector<vector<int>> &res, vector<int> &path, vector<int> &candidates, int target, int start) { // 因为数组中的元素都是正数,所以这里当target <= 0的时候要终止 if (target <= 0) { if (target == 0) // 如果找到一组解就把他保存下来 res.emplace_back(path); return; } // 这里要注意,因为不能有重复的组合,所以循环的起始位置不是0, // 否则会出现类似于[1,2]和[2,1]这种重复的组合。 for (int i = start; i < candidates.size(); i++) { // 递归的三步走,选择当前元素 path.emplace_back(candidates[i]); // 递归,到树的下一层,这里target要减去当前元素的值 dfs(res, path, candidates, target - candidates[i], i); // 递归往回走要撤销选择 path.pop_back(); } }
void dfs(int **ans, int *path, int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes, int start, int count) { // 因为数组中的元素都是正数,所以这里当target <= 0的时候要终止 if (target <= 0) { if (target == 0) {// 如果找到一组解就把他保存下来 ans[*returnSize] = malloc(count * sizeof(int)); memcpy(ans[*returnSize], path, count * sizeof(int)); (*returnColumnSizes)[*returnSize] = count; (*returnSize)++; } return; } // 这里要注意,因为不能有重复的组合,所以循环的起始位置不是0, // 否则会出现类似于[1,2]和[2,1]这种重复的组合。 for (int i = start; i < candidatesSize; i++) { // 递归的三步走,选择当前元素 path[count++] = candidates[i]; // 递归,到树的下一层,这里target要减去当前元素的值 dfs(ans, path, candidates, candidatesSize, target - candidates[i], returnSize, returnColumnSizes, i, count); // 递归往回走要撤销选择 count--; } }
int **combinationSum(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) { int **ans = malloc(150 * sizeof(int *));// 返回的结果集 int *path = malloc(30 * sizeof(int));// *returnSize = 0; *returnColumnSizes = malloc(150 * sizeof(int)); dfs(ans, path, candidates, candidatesSize, target, returnSize, returnColumnSizes, 0, 0); return ans; }
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(t: int, start: int): # 因为数组中的元素都是正数,所以这里当target <= 0的时候要终止 if t <= 0: if t == 0: # 如果找到一组解就把他保存下来 ans.append(path[:]) return # 这里要注意,因为不能有重复的组合,所以循环的起始位置不是0, # 否则会出现类似于[1, 2]和[2, 1]这种重复的组合。 for i in range(start, len(candidates)): # 递归的三步走,选择当前元素 path.append(candidates[i]) # 递归,到树的下一层,这里target要减去当前元素的值 dfs(t - candidates[i], i) # 递归往回走要撤销选择 path.pop()
ans = [] # 返回的结果集 path = [] dfs(target, 0) return ans
博哥,真名:王一博,毕业十多年,《算法秘籍》作者,专注于数据结构和算法的讲解,在全球30多个算法网站中累计做题2000多道,在公众号中写算法题解800多题,对算法题有自己独特的解题思路和解题技巧,喜欢的可以给个关注,也可以下载我整理的1000多页的PDF算法文档。
|