Given an array of distinct integer 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.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Examples 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 candidates, and 7 = 7.
- These are the only two combinations.
- Input: candidates = [2,3,5], target = 8
- Output: [[2,2,2,2],[2,3,3],[3,5]]
- Input: candidates = [2], target = 1
- Output: []
- 1<= candidates.length <= 30
- 2 <= candidates[i] <= 40
- All elements of candidates are distinct.
- 1 <= target <= 40
-----------------------------------------------------------------------------------------------------------------------------
Solution
Since the
given candidates are unique, if we can simply sort the array we can iterate
over the same to find all combinations of elements which forms the sum equals
to target.
"Sorting"
is only used to make the finding of combination efficient, where we can ignore
the further elements if the current sum itself is greater than the target. So
one can solve this withoug sorting also.
Also, we
need to consider that the sum can be formed using the same element multiple
times.
We use
backtracking to solve this, where we'll also recursively perform the operations
on same index position too for considering the same element multiple times.
Complexity
Time
complexity:
O(target *
(2^N))
"2^N"
part due to recursion and backtracking while trying to accomodate individual
elements once in the sum (in simple words, to find the subset ofunique
elements)
"* target" as individual elements can be
Space
complexity:
O(target *
(2^N)) - due to the number of recursion - stack memory used
Code
Recursion, backtracking, moving always from left to right.
ReplyDeleteIntuition
We technically need to try all combinations, but we can somewhat optimize our approach by sorting candidates:
we may ignore all candidates that exceed target, if any
we may move in one direction and probe only candidates with themselves and with greater candidates - no need to go both directions. So it is less than NxN
Approach
I sort the candidates and then loop each of them in one pass (but stop when I reach the first one exceeding target) first. For each such candidate, I then try (or probe) to recursevely sum it with all other greater candidates. Also I keep adding candidate to itself and then again try all other greater candidates. Each time I stop if the sum matches our target (so I add all probed candidates to the answer) or if the sum eventually exceeds the target - so I backtrack and try the next combination.
I use the List called "probe" for backtracking.
Code
public class Solution {
public IList> CombinationSum(int[] candidates, int target) {
List> ret = new();
Array.Sort(candidates);//values are distinct but not necesserily sorted
//The max target is 40, so no more than 40 candidates can comprise it (if all are ones)
List probe = new(40);
for (int i = 0; i < candidates.Length; i++) {
if (candidates[i] > target) break; //no reason to continue
CombinationSumSub(candidates, ret, target, i, probe);
}
return ret;
}
private void CombinationSumSub(int[] candidates,List> ret, int target, int ind, List probe=null, int accumlatedSum=0) {
int n = candidates[ind];
int remain = target - accumlatedSum;
if (n > remain) return;
int nn = 0, cntAdded = 0;
while (n <= remain) {
if (n == remain) {
int probeCnt = probe == null ? 0 : probe.Count;
List lst = new(probeCnt + 1);
ret.Add(lst);
if (probeCnt > 0) lst.AddRange(probe);
lst.Add(n);//we didn't have a chance to add it to the "probe" - and don't need anymore
if (lst.Count == 149) return; //by problem's definition - they guarantee less than 150 combinations in the result
break;
} else {
probe.Add(n);
cntAdded++;
remain -= n;
nn += n;
int newSum = accumlatedSum + nn;
for (int j = ind+1; j < candidates.Length; j++) {
if (candidates[j] > remain) break;
CombinationSumSub(candidates, ret, target, j, probe, newSum);
}
}
}
//remove anything added in this iteration for backtracing
if (cntAdded>0) probe.RemoveRange(probe.Count - cntAdded, cntAdded);
}
}
Solution in Java
ReplyDeleteProper Step by step Explanation|| SIMPLEST APPROACH
Intuition
The code follows a backtracking approach to find all combinations that sum up to the given target.
Approach
The code follows a backtracking approach to find all combinations that sum up to the given target.
The combinationSum method is the entry point for the backtracking process. It initializes the ans list to store the result and the ls list to track the current combination.
The cum method performs the backtracking. It takes the current array c, the remaining target value, and the starting index as parameters.
The base case is when the target value becomes zero. In this case, it means that the current combination in ls sums up to the target. Therefore, a copy of ls is added to the ans list as a valid combination.
The for loop iterates through the elements in the c array, starting from the given index start.
Within the loop, if the current element c[i] is less than or equal to the remaining target, it is a valid candidate to include in the combination.
The element c[i] is added to the ls list, and the cum method is recursively called with the updated target (subtracting c[i]) and the same starting index i to allow reusing the same element in subsequent combinations.
After the recursive call, the last element is removed from ls using ls.remove(ls.size() - 1). This step is crucial for backtracking, as it ensures that the correct elements are considered for the next iteration of the loop.
The process continues with the next element in the loop until all combinations have been explored.
Complexity
Time complexity: O(2^N)
Space complexity: O(2^N)
Code
class Solution {
List> ans = new ArrayList<>();
ArrayList ls = new ArrayList<>();
public List> combinationSum(int[] c, int target) {
cum(c, target, 0);
return ans;
}
public void cum(int[] c, int target, int start) {
if (target == 0) {
ans.add(new ArrayList<>(ls));
return;
}
for (int i = start; i < c.length; i++) {
if (c[i] <= target) {
ls.add(c[i]);
cum(c, target - c[i], i);
ls.remove(ls.size() - 1);
}
}
}
}