<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>

#include <vector>
#include <queue>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        return BFS(candidates, target);
    }

private:

std::vector<std::vector<int>> combinationSumDP(std::vector<int>& candidates, int target) {
    // DP table where dp[i] stores all combinations that sum up to i
        std::vector<std::vector<std::vector<int>>> dp(target + 1);

        dp[0] = {{}};

        // Iterate over each candidate
        for (int candidate : candidates) {
            // Update dp array for each target sum from the current candidate to the target
            for (int i = candidate; i <= target; ++i) {
                // For each combination that leads to 'i - candidate', add 'candidate' to form 'i'
                for (const auto& combination : dp[i - candidate]) {
                    std::vector<int> newCombination = combination;
                    newCombination.push_back(candidate);
                    dp[i].push_back(newCombination);
                }
            }
        }

        // Return the combinations that sum up to 'target'
        return dp[target];
    }





    std::vector<std::vector<int>> BFS(std::vector<int>& candidates, int target)
    {
        std::queue<std::tuple<std::vector<int>, int, int>> q;
        std::vector<std::vector<int>> result;

        // Start with an empty combination, sum 0, and index 0
        q.push({std::vector<int>{}, 0, 0});

        while (!q.empty())
        {
            auto [currentCombination, sum, idx] = q.front();
            q.pop();

            // If we reach the target sum, add the combination to the result
            if (sum == target)
            {
                result.push_back(currentCombination);
                continue;
            }

            // Try adding each candidate starting from index `idx`
            for (int i = idx; i < candidates.size(); ++i)
            {
                // Create a new combination that includes candidates[i]
                std::vector<int> newCombination = currentCombination;
                newCombination.push_back(candidates[i]);

                // Calculate new sum
                int newSum = sum + candidates[i];

                // Only push the new state if newSum is <= target
                if (newSum <= target) {
                    q.push({newCombination, newSum, i});  // Pass 'i' to allow reuse of the same candidate
                }
            }
        }

        return result;
    }





    std::vector<std::vector<int>> DFS(std::vector<int>& candidates, int target)
    {
        std::vector<std::vector<int>> result;
        std::vector<int> current_combination;
        // Start recursion from index 0
        DFS_helper(current_combination, 0, target, candidates, result);
        return result;
    }

    void DFS_helper(std::vector<int>& current_combination, int currIdx, int target, std::vector<int>& candidates, 
                    std::vector<std::vector<int>>& result)
    {
        // Calculate the sum of current_combination
        int sum = 0;
        for (int num : current_combination)
        {
            sum += num;
        }

        // If the sum equals the target, we found a valid combination
        if (sum == target)
        {
            result.push_back(current_combination);
            return;
        }

        // If the sum exceeds the target, stop exploring this path
        if (sum > target)
        {
            return;
        }

        // Explore further by including candidates starting from currIdx
        for (int i = currIdx; i < candidates.size(); ++i)
        {
            // Add the current candidate to the current combination
            current_combination.push_back(candidates[i]);

            // Recursively call DFS_helper with the same index i (to allow reuse)
            DFS_helper(current_combination, i, target, candidates, result);

            // Backtrack: remove the last added element to explore other combinations
            current_combination.pop_back();
        }
    }

};
24500