<p>Given an array of <strong>distinct</strong> integers <code>candidates</code> and a target integer <code>target</code>, return <em>a list of all <strong>unique combinations</strong> of </em><code>candidates</code><em> where the chosen numbers sum to </em><code>target</code><em>.</em> You may return the combinations in <strong>any order</strong>.</p>

<p>The <strong>same</strong> number may be chosen from <code>candidates</code> an <strong>unlimited number of times</strong>. Two combinations are unique if the <span data-keyword="frequency-array">frequency</span> of at least one of the chosen numbers is different.</p>

<p>The test cases are generated such that the number of unique combinations that sum up to <code>target</code> is less than <code>150</code> combinations for the given input.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> candidates = [2,3,6,7], target = 7
<strong>Output:</strong> [[2,2,3],[7]]
<strong>Explanation:</strong>
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> candidates = [2,3,5], target = 8
<strong>Output:</strong> [[2,2,2,2],[2,3,3],[3,5]]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> candidates = [2], target = 1
<strong>Output:</strong> []
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= candidates.length &lt;= 30</code></li>
	<li><code>2 &lt;= candidates[i] &lt;= 40</code></li>
	<li>All elements of <code>candidates</code> are <strong>distinct</strong>.</li>
	<li><code>1 &lt;= target &lt;= 40</code></li>
</ul>

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> output;
        set<vector<int>> uniqueCombinations;
        
        function<void(vector<int>, int)> recursion = [&](vector<int> currArr, int currTarget) {
            if (currTarget == 0) {
                vector<int> sortedCurrArr = currArr;
                sort(sortedCurrArr.begin(), sortedCurrArr.end());
                if (uniqueCombinations.find(sortedCurrArr) == uniqueCombinations.end()) {
                    uniqueCombinations.insert(sortedCurrArr);
                    output.push_back(sortedCurrArr);
                }
                return;
            }
            for (int num : candidates) {
                if (currTarget - num >= 0) {
                    currArr.push_back(num);
                    recursion(currArr, currTarget - num);
                    currArr.pop_back(); // backtrack
                }
            }
        };
        
        recursion({}, target);
        return output;
    }
};
/*
Backtracking with Recursion:

Define a recursive helper function to explore all possible combinations.
Use a list temp to store the current combination and a list ans to store all valid combinations.
Start from the first candidate and explore two paths: including the candidate and not including the candidate.
If the current sum equals the target, add the current combination to the answer list.
If the current sum exceeds the target or the index exceeds the length of candidates, backtrack by removing the last added candidate and exploring the next candidate.
Recursive Function:

Base Case: If the sum of the current combination equals the target, add the combination to the answer list.
If the sum exceeds the target or if there are no more candidates to consider, return to explore other paths.
Recursive Case: Include the current candidate and call the function with the updated sum. Exclude the current candidate and call the function with the next candidate.
Start the Recursion:

Start the recursion from the first index and an initial sum of 0.
*/
64500