欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

组合总数

程序员文章站 2024-03-15 08:34:29
...

题目

组合总数

思路

本题是给定一个正整数和数组,要求在数组中找出所有可以使数字和为该正整数的组合,其中数组中的数字可以重复使用
组合总数
如上图:
可以看出,当我们的target值小于等于0时便停止搜寻,所以回溯递归的基准条件就是当target小于等于0。相关代码如下:

class Solution {
public:
    vector<vector<int>> res;
	vector<int> path;
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		if (candidates.size() == 0)return res;
		sort(candidates.begin(), candidates.end());
		dfs(candidates,0,candidates.size()-1,target);
		return res;
	}
	void dfs(vector<int> candidates,int left,int right, int target) {
		if (target == 0) {//当target为0,说明此时已经找到符合条件的数组
			res.push_back(path);
			return;
		}
		if (target < 0)return;
		for (int i = left; i <=right; i++) {
				path.push_back(candidates[i]);
				dfs(candidates, i, right, target - candidates[i]);
				path.pop_back();
			}
		}
};
相关标签: LeetCode