# LeetCode 039Combination Sum

## LeetCode 039 Combination Sum Problem

``````class Solution(object):
# def combinationSum(self, candidates, target):
#     """
#     :type candidates: List[int]
#     :type target: int
#     :rtype: List[List[int]]
#     """
#     candidates.sort()
#     return self.getcombinationSum(candidates, [], 0, target)
#
#
# def getcombinationSum(self, candidates, prefix, curr, target):
#     if len(prefix) == 0:
#         max_value = candidates[0]
#     else:
#         max_value = prefix[-1]
#     res = []
#     for i in range(len(candidates)):
#         if candidates[i] >= max_value:
#             if curr + candidates[i] == target:
#                 res.append(prefix+[candidates[i]])
#             elif curr + candidates[i] < target:
#                 res.extend(self.getcombinationSum(candidates, prefix+[candidates[i]], curr + candidates[i], target))
#             else:
#                 pass
#     return res

def combinationSum(self, candidates, target):
candidates.sort()
dp = [[] for _ in range(target + 1)]
dp[0].append([])
for i in range(1, target + 1):
for j in range(len(candidates)):
if candidates[j] > i:
break
for k in range(len(dp[i - candidates[j]])):
temp = dp[i - candidates[j]][k][:]
if len(temp) > 0 and temp[-1] > candidates[j]:
continue
temp.append(candidates[j])
dp[i].append(temp)
return dp[target]

if __name__ == '__main__':
s = Solution()
print s.combinationSum([8,7,4,3], 11)

``````
Download Combination Sum.py

## List of all Combination Sum problems

Leetcode 039 Combination Sum problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.