# 39. Combination Sum

Check the problem description here

*Solution .*

*Recursion*

Go on choosing the element at current index and thereby reduce the required sum by that element, if required sum is got add it to the result, else if the sum is <0 then return to the caller and check if the next elements from the array can be chosen or not.

*You can call the recursion after sorting the array or not. If you sort the array you can effectively calculate the time complexity.*

`class Solution:`

def combinationSum(self, candidates,target):

result=[]

candidates.sort() # not necessary

self.rec(candidates,0,[],target,result)

return result

def rec(self,candidates,ind,ds,target,result):

if target<0:

return

elif target == 0 :

result.append(ds)

else:

for i in range(ind,len(candidates)):

self.rec(candidates,i,ds+[candidates[i]],target-candidates[i],result)

Time :**O(N^(T/M + 1))** where N is the number of candidates, M is the smallest candidate among all the given integers, and T is the target value. Thus the time complexity is exponential and this is expected because the algorithm is recursive backtracking.

Space :**O(T/M),**

where T is the target value and M is the minimal element among all other candidates.