This approach uses recursion and backtracking to generate all possible combinations by exploring each candidate. If a candidate is chosen, we explore further with the remaining target reduced by the candidate's value. We use backtracking to remove a candidate and try the next one. This way, we explore all possible combinations using depth-first search.
Time Complexity: O(2^T), where T is the target, as it potentially explores every combination of the candidates.
Space Complexity: O(T) for the recursion call stack and the path being explored.
1using System;
2using System.Collections.Generic;
3
4class CombinationSumSolution {
5 public IList<IList<int>> CombinationSum(int[] candidates, int target) {
6 IList<IList<int>> result = new List<IList<int>>();
7 List<int> tempList = new List<int>();
8 Backtrack(candidates, target, result, tempList, 0);
9 return result;
10 }
11
12 private void Backtrack(int[] candidates, int target, IList<IList<int>> result, List<int> tempList, int start) {
13 if (target < 0) return;
14 if (target == 0) result.Add(new List<int>(tempList));
15 for (int i = start; i < candidates.Length; i++) {
16 tempList.Add(candidates[i]);
17 Backtrack(candidates, target - candidates[i], result, tempList, i);
18 tempList.RemoveAt(tempList.Count - 1);
19 }
20 }
21
22 static void Main(string[] args) {
23 int[] candidates = {2, 3, 6, 7};
24 int target = 7;
25 CombinationSumSolution solution = new CombinationSumSolution();
26 var result = solution.CombinationSum(candidates, target);
27 foreach (var combination in result) {
28 Console.WriteLine("[" + string.Join(", ", combination) + "]");
29 }
30 }
31}
32The C# solution follows a similar recursive backtracking approach. The Backtrack method verifies candidates by reusing them based on the same recursive index and tracks valid sets in result.
We can use a dynamic programming (DP) approach to solve the Combination Sum problem. We maintain a DP array where each index represents the number of ways to form that particular sum using the candidates. The approach involves iterating through candidates and updating the DP array for each possible sum that can be formed with that candidate.
Time Complexity: Roughly O(T * N), for target T and candidates N.
Space Complexity: O(T) for the dp array itself in context of storage.
1def combinationSum(candidates, target):
2 dp = [[] for _ in range(target + 1)]
3 dp[0] = [[]]
4
5 for candidate in candidates:
6 for i in range(candidate, target + 1):
7 for sublist in dp[i - candidate]:
8 dp[i].append(sublist + [candidate])
9 return dp[target]
10
11candidates = [2, 3, 6, 7]
12target = 7
13print(combinationSum(candidates, target))
14The Python implementation uses a dynamic programming step-up approach where each candidate helps form every possible sum from itself up to the target by utilizing previous built combination lists at dp indices.