> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/medium/combination-sum.md).

# Combination Sum

## [Combination Sum](https://leetcode.com/problems/combination-sum)

Given an array of **distinct** integers `candidates` and a target integer `target`, return *a list of all **unique combinations** of* `candidates` *where the chosen numbers sum to* `target`*.* You may return the combinations in **any order**.

The **same** number may be chosen from `candidates` an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is **guaranteed** that the number of unique combinations that sum up to `target` is less than `150` combinations for the given input.

**Example 1:**

```

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
```

**Example 2:**

```

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
```

**Example 3:**

```

Input: candidates = [2], target = 1
Output: []
```

**Example 4:**

```

Input: candidates = [1], target = 1
Output: [[1]]
```

**Example 5:**

```

Input: candidates = [1], target = 2
Output: [[1,1]]
```

**Constraints:**

* `1 <= candidates.length <= 30`
* `1 <= candidates[i] <= 200`
* All elements of `candidates` are **distinct**.
* `1 <= target <= 500`

## Solutions

### 🧠 Cpp

```cpp
class Solution
{
private:
    struct input
    {
        input(vector<int> a, int b) : allowed_nums(a), target(b) {}
        bool operator<(input const &b) const
        {
            return target < b.target;
        }
        vector<int> allowed_nums;
        int target;
    };

    map<input, vector<vector<int>> > combinationSums;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        //DP part
        {
            input a = {candidates, target};
            auto DP_res = combinationSums.find(a);
            if(DP_res != end(combinationSums))
                return DP_res->second;
        }

        set<vector<int>> res;
        for(int candidate : candidates)
        {
            if(target < candidate)
                continue;
            else if(target == candidate)
            {
                res.insert({candidate});
            }
            else if(target > candidate)
            {
                vector<vector<int>> sub_res = combinationSum(candidates, target-candidate);
                if(sub_res.empty())
                    continue;

                //if we have valid sub_res:
                for(auto &v : sub_res)
                {
                    v.push_back(candidate);
                    std::sort(begin(v), end(v));
                }

                //add this to result
                res.insert(begin(sub_res), end(sub_res));
            }
        }

        //DP memoization
        input a = {candidates, target};
        combinationSums.insert(pair<input, vector< vector <int> > >(a, {res.begin(), res.end()}));

        return {res.begin(), res.end()};
    }
};
```