（算法）组合总和————＜递归＞

1. 题⽬链接：39.组合总和 

2. 题⽬描述：

3. 解法：

算法思路：

candidates的所有元素互不相同，因此我们在递归状态时只需要对每个元素进⾏如下判断：

1. 跳过，对下⼀个元素进⾏判断；

2. 将其添加⾄当前状态中，我们在选择添加当前元素时，之后仍可以继续选择当前元素（可以重复选 择同⼀元素）。

• 因此，我们在选择当前元素并向下传递下标时，应该直接传递当前元素下标。

递归函数设计：void dfs(vector& candidates, int target, vector>& ans, vector& combine, int idx)  

参数：target（当前状态和与⽬标值的差），idx（当前需要处理的元素下标）；

返回值：⽆；

函数作⽤：向下传递两个状态（跳过或者选择当前元素），找出所有组合使得元素和为⽬标值。

递归函数流程如下：

1. 结束条件：

        a. 当前需要处理的元素下标越界；

        b. 当前状态的元素和已经与⽬标值相同；

2. 跳过当前元素，当前状态不变，对下⼀个元素进⾏处理；

3. 选择将当前元素添加⾄当前状态，并保留状态继续对当前元素进⾏处理，递归结束时撤销添加操作。 

C++算法代码： 

class Solution
{
	int aim;
	vector<int> path;
	vector<vector<int>> ret;
public:
	vector<vector<int>> combinationSum(vector<int>& nums, int target)
	{
		aim = target;
		dfs(nums, 0, 0);
		return ret;
	}
	void dfs(vector<int>& nums, int pos, int sum)
	{
		if (sum == aim)
		{
			ret.push_back(path);
			return;
		}
		if (sum > aim || pos == nums.size()) return;
		// 枚举个数 
		for (int k = 0; k * nums[pos] + sum <= aim; k++)
		{
			if (k) path.push_back(nums[pos]);
			dfs(nums, pos + 1, sum + k * nums[pos]);
		}
		// 恢复现场 
		for (int k = 1; k * nums[pos] + sum <= aim; k++)
		{
			path.pop_back();
		}
	}
};

Java算法代码：

class Solution
{
	int aim;
	List<Integer> path;
	List<List<Integer>> ret;
	public List<List<Integer>> combinationSum(int[] nums, int target)
	{
		path = new ArrayList<>();
		ret = new ArrayList<>();
		aim = target;
		dfs(nums, 0, 0);
		return ret;
	}
	public void dfs(int[] nums, int pos, int sum)
	{
		if (sum == aim)
		{
			ret.add(new ArrayList<>(path));
			return;
		}
		if (sum > aim || pos == nums.length) return;
		// 枚举 nums[pos] 使⽤多少个 
		for (int k = 0; k * nums[pos] + sum <= aim; k++)
		{
			if (k != 0) path.add(nums[pos]);
			dfs(nums, pos + 1, sum + k * nums[pos]);
		}

		// 恢复现场 
		for (int k = 1; k * nums[pos] + sum <= aim; k++)
		{
			path.remove(path.size() - 1);
		}
	}
}