Find all set of elements to express n as a sum of a given list.
Example:
If A = {2,3,6,7}, n = 7
Ans: {2,2,3} and {7}
Solutions:
This problem is can be solved by solving the sub problems (dynamic programing) using recursion.
Basically, we have the option to include or not to include {2,3,6,7} in each result.
Therefore, for example when we don't need 2 in the result, we have to remove it also from the given sum (eg 7-2 => sum = 5)
Therefore the solution is adding each sub solution by including and excluding {2,3,6,7} from the list.
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
List<IList<int>> ans = new List<IList<int>>();
BackTrack(candidates,0, target,new List<int>(), ans);
return ans;
}
public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result) {
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));
for (int i = start; i < cand.Length; i++) {
list.Add(cand[i]);
BackTrack(cand, i, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}
In case of duplicate elements are not allowed in the result set, in other words we should us each element of the array only once when we add up to make the sum, we just need to add two things to the above code:
- Sort the candidates array since we want to compare adjacent numbers in candidate and see if they are the same, if so we ignore it
- Just add a simple check to compare adjacent numbers
if (i > start && cand[i] == cand[i - 1]) continue; // skip duplicates
Here is the entire code:
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
List<IList<int>> ans = new List<IList<int>>();
Array.Sort(candidates);
BackTrack(candidates,0, target,new List<int>(), ans);
return ans;
}
public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result) {
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));
for (int i = start; i < cand.Length; i++) {
if (i > start && cand[i] == cand[i - 1]) continue; // skip duplicates
list.Add(cand[i]);
BackTrack(cand, i+1, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}