# Combination Sum I, II and III Java solution (see the similarities yourself)

• Combination Sum I

``````public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(candidates);
backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
if (remain < 0) return; /** no solution */
else if (remain == 0) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i < cand.length; i++) {
backtrack(list, tempList, cand, remain-cand[i], i);
tempList.remove(tempList.size()-1);
}
}

}
``````

Combination Sum II

``````public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new LinkedList<List<Integer>>();
Arrays.sort(candidates);
backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {

if(remain < 0) return; /** no solution */
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i < cand.length; i++) {
if(i > start && cand[i] == cand[i-1]) continue; /** skip duplicates */
backtrack(list, tempList, cand, remain - cand[i], i+1);
tempList.remove(tempList.size() - 1);
}
}
}
``````

Combination Sum III

``````public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<Integer>(), k, n, 1);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int remain, int start) {
if(tempList.size() > k) return; /** no solution */
else if(tempList.size() == k && remain == 0) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i <= 9; i++) {
backtrack(list, tempList, k, remain-i, i+1);
tempList.remove(tempList.size() - 1);
}
}
}``````

• ``````def __init__(self):
self.result = []
self.candidates = []

def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.candidates = candidates
self.findCombinations(0, [], target)
return self.result

def findCombinations(self, index, data, n):

if(n<0):
return
if(n == 0):
self.result.append(data)
return
if(index==self.candidates.__len__()):
return
visitedIndex = None
for i in range(index,self.candidates.__len__()):
if visitedIndex != self.candidates[i]:
self.findCombinations(i+1, data+[self.candidates[i]], n-self.candidates[i])
visitedIndex = self.candidates[i]``````

• Hi

Awesome compilations of all the three solutions. Could you please tell me why we need the condition "i > start" in the second combination problem where we skip duplicates?

• @issac3 Why do we need to sort the element in the First case i.e. Combination Sum 1?

• good summary, thx

• Thank you so much for summarizing the similarities in a succinct manner.

Can anyone please state and explain the time complexity of these solutions? Would it be O(2^n)? Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.