# 组合总和

<p>给定一个<strong>无重复元素</strong>的数组&nbsp;<code>candidates</code>&nbsp;和一个目标数&nbsp;<code>target</code>&nbsp;，找出&nbsp;<code>candidates</code>&nbsp;中所有可以使数字和为&nbsp;<code>target</code>&nbsp;的组合。
</p>
<p><code>candidates</code>&nbsp;中的数字可以无限制重复被选取。</p>
<p><strong>说明：</strong></p>
<ul>
    <li>所有数字（包括&nbsp;<code>target</code>）都是正整数。</li>
    <li>解集不能包含重复的组合。&nbsp;</li>
</ul>
<p><strong>示例&nbsp;1：</strong></p>
<pre><strong>输入：</strong>candidates = [2,3,6,7], target = 7,<strong><br />输出：</strong>[[7],[2,2,3]]</pre>
<p><strong>示例&nbsp;2：</strong></p>
<pre><strong>输入：</strong>candidates = [2,3,5], target = 8,<strong><br />输出：</strong>[[2,2,2,2],[2,3,3],[3,5]]</pre>
<p>&nbsp;</p>
<p><strong>提示：</strong></p>
<ul>
    <li><code>1 &lt;= candidates.length &lt;= 30</code></li>
    <li><code>1 &lt;= candidates[i] &lt;= 200</code></li>
    <li><code>candidate</code> 中的每个元素都是独一无二的。</li>
    <li><code>1 &lt;= target &lt;= 500</code></li>
</ul>
<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<vector<int>> res;
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;

    res = sol.combinationSum(candidates, target);

    for (auto i : res)
    {
        for (auto j : i)
            cout << j << " ";
        cout << endl;
    }
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        set<vector<int>> res;
        vector<int> temp;
        sort(candidates.begin(), candidates.end());
        fun(candidates, target, 0, temp, res);
        vector<vector<int>> result;
        for (auto mem : res)
        {
            result.push_back(mem);
        }
        return result;
    }

    void fun(const vector<int> &candidates, int target, int index, vector<int> &temp, set<vector<int>> &res)
    {
        if (target < 0)
            return;
        if (target == 0)
        {
            res.insert(temp);
            return;
        }
        while (index < candidates.size())
        {
            temp.push_back(candidates[index]);
            fun(candidates, target - candidates[index], index + 1, temp, res);
            temp.pop_back();
            ++index;
        }
    }
};
```
## 选项


### A

```cpp

class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        dfs(candidates, 0, target, res);
        return res;
    }

private:
    vector<int> stack;
    void dfs(vector<int> &candidates, int start, int target, vector<vector<int>> &res)
    {
        if (target < 0)
        {
            return;
        }
        else if (target == 0)
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                stack.push_back(candidates[i]);
                dfs(candidates, i, target - candidates[i], res);
                stack.pop_back();
            }
        }
    }
};
```

### B

```cpp
class Solution
{
public:
    void compute(int start, int target, vector<int> &tmp, vector<int> &candidates, vector<vector<int>> &ans)
    {
        int n = candidates.size();
        for (int i = start; i < n; i++)
        {
            if (target > 0)
            {
                tmp.push_back(candidates[i]);
                compute(i, target - candidates[i], tmp, candidates, ans);
                tmp.pop_back();
            }
            else if (target < 0)
                return;
            else
            {
                ans.push_back(tmp);
                return;
            }
        }
    }

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

        int v;

        sort(candidates.begin(), candidates.end());
        compute(0, target, tmp, candidates, ans);

        return ans;
    }
};
```

### C

```cpp
class Solution
{
private:
    vector<vector<int>> res;
    vector<int> ans;

public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        int left = 0, right = 0;
        for (; right < candidates.size() && candidates[right] <= target; right++)
            ;
        backtrack(candidates, left, right == candidates.size() ? right - 1 : right, target);
        return res;
    }

private:
    void backtrack(vector<int> &candidates, int left, int right, int target)
    {
        if (target < 0)
            return;
        if (!target)
        {
            res.push_back(ans);
            return;
        }
        for (int i = left; i <= right && candidates[i] <= target; i++)
        {
            ans.push_back(candidates[i]);
            backtrack(candidates, i, right, target - candidates[i]);
            ans.pop_back();
        }
    }
};
```