BiruLyu
5/31/2017 - 3:32 AM

## 39. Combination Sum.java

``````class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""

#if not candidates:
#   return [[]]

candidates.sort()
res = []
self.backtracking(candidates, target, 0, [], res)
return res

def backtracking(self, candidates, target, start, temp, res):
if target == 0:
return res.append(temp);

for i in range(start,len(candidates)):
if target< candidates[i]:
return;# Save some time
self.backtracking(candidates, target - candidates[i], i, temp + [(candidates[i])], res) # Do not use return

"""
TESTCASES:
Input:
[2,3,6,7]
7
[2,2,2,2]
4
[1]
1
[]
0

Output:
[[2,2,3],[7]]
[[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2],[2,2]]
[[1]]
[[]]

"""``````
``````public class Solution {
public void backtracking(int[] candidates, int target, int start,List<Integer> temp, List<List<Integer>> res){
if(target == 0){
return;
}
for(int i = start; i < candidates.length; i++){
if(target < candidates[i]) return;