组合总和问题

11 Sep 2024 in Algorithm Pageviews

模板

组合总和的方案求解问题求解通常与回溯紧密相连。

组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入:

candidates = [10,1,2,7,6,1,5], target = 8

输出:

[[1,1,6],[1,2,5],[1,7],[2,6]]

示例 2:

输入:

candidates = [2,5,2,1,2], target = 5

输出:

[[1,2,2],[5]]

代码实现如下:

class Solution {
public:
    void helper(vector<int> &people, int u, int target)
    {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.push_back(path);
            return;
        }

        for (size_t i = u; i < people.size(); i++) {
            if ((i > u) && people[i] == people[i - 1]) {
                continue;
            }

            path.push_back(people[i]);
            helper(people, i + 1, target - people[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& people, int target) {
        sort(people.begin(), people.end());
        helper(people, 0, target);
        return result;
    }

    vector<int> path;
    vector<vector<int>> result;
};