Combination Sum medium

Problem Statement

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's guaranteed that the number of unique combinations is at most 1000.

Example 1

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates. 2 + 2 + 3 = 7. Also 7 is a candidate.

Example 2

Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] Explanation: 2, 3, and 5 are candidates. 2 + 2 + 2 + 2 = 8, 2 + 3 + 3 = 8, 3 + 5 = 8.

Steps

1. Sort the candidates: Sorting allows us to efficiently prune the search space later.

2. Backtracking function: We'll use a recursive backtracking function to explore all possible combinations. This function takes the following arguments:

   • index: The current index in the candidates array.
   • combination: The current combination being built.
   • remaining: The remaining sum needed to reach the target.
   • result: A list to store the final combinations.

3. Base Cases:

   • If remaining is 0, we've found a valid combination, so add combination to result.
   • If remaining is negative or index is out of bounds, we've gone beyond the target or exhausted all candidates, so we backtrack.

4. Recursive Step: For each candidate at the current index:

   • Include the candidate: Add it to combination, update remaining, and recursively call the function with the same index (since we can reuse the same candidate).
   • Exclude the candidate: Recursively call the function with the next index (index + 1).

5. Return the result: After exploring all possibilities, return the result list.

Explanation

The backtracking approach systematically explores all possible combinations. Sorting the candidates helps to optimize the search by avoiding unnecessary explorations. The recursive calls with the same index allow for the selection of the same number multiple times. The base cases handle the termination conditions efficiently.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates); // Sort for optimization
        IList<IList<int>> result = new List<IList<int>>();
        Backtrack(candidates, target, 0, new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] candidates, int remaining, int index, List<int> combination, IList<IList<int>> result) {
        if (remaining == 0) {
            result.Add(new List<int>(combination)); // Add a copy to avoid modification
            return;
        }
        if (remaining < 0 || index >= candidates.Length) {
            return; // Base case: exceeded target or exhausted candidates
        }

        // Include the current candidate
        combination.Add(candidates[index]);
        Backtrack(candidates, remaining - candidates[index], index, combination, result); // Same index for reuse

        // Exclude the current candidate
        combination.RemoveAt(combination.Count - 1);
        Backtrack(candidates, remaining, index + 1, combination, result); // Move to next candidate
    }
}

Complexity

• Time Complexity: O(N^T), where N is the number of candidates and T is the target value. In the worst case, we might explore all possible combinations.
• Space Complexity: O(T) in the worst case, due to the recursive call stack and the maximum depth of the combination list. The space used for the result list is proportional to the number of combinations, which is also bounded by O(N^T).