LeetCode 39 组合总和 - 回溯解法

https://leetcode.cn/problems/combination-sum/description/

思路

类似于[组合](LeetCode 77 组合 - 回溯解法.md)，这里要求路径总和等于 target。

手动模拟

candidates = [2,3,6,7]，target = 7。先把 2 放入 path，下一层仍然可以从 2, 3, 6, 7 里选。这和[组合](LeetCode 77 组合 - 回溯解法.md)不同：本题允许重复选同一个数，所以可能连续选择同一元素。用 sum 控制递归边界，sum > target 时直接返回。

两部分

确定函数输入： start：开始下标。 end：结束下标。 sum：当前 path 总和。 target：目标总和。

直接返回。
1. sum==target 保存结果，返回
2. sum>target 不保存，返回
进一步调用。
1. 函数语义：从 start 到 end 中选一个数。
2. 为了遍历所有情况，需要 for 循环。i 是本层选中的数，下一层仍然从 i 开始（允许重复选择当前数）。

伪代码

function  sel_num(start, end, sum, target){
	if(sum==target) 保存  return
	//为了防止无限的加入
	if(sum> target) 不保存 return

	for(i, i<=end, i++){
		path.push_back(shuzu[i])
		// 下一层仍然允许从当前 i 开始（可重复），但 sum 需要更新。
		sel_num(start, end, sum+shuzu[i], target)
		path.pop_back()
	}
}

代码

class Solution {

public:

    vector<int> path;

    vector<vector<int>> result;

	//存储数组, 不然sel_number拿不到 candidate数组
    vector<int> loc_candidates;

    void sel_number(int start, int end, int current_sum, int target) {

            if (current_sum == target) {

                result.push_back(path);

                return;

            }
			//不保存, 直接返回
            if(current_sum > target) return;

            for (int i = start; i <= end; i++) {

                path.push_back(loc_candidates[i]);
				//sum 要及时更新
                sel_number(i, end, current_sum + loc_candidates[i], target);

                path.pop_back();

            }

        }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        loc_candidates = candidates;

        sel_number(0,candidates.size()-1, 0, target);

        return result;

    }

};