首页 > itarticle > leetcode 39 — combination sum Solution Result

leetcode 39 — combination sum Solution Result

admin 11月 11, 2020 0

Category	Difficulty	Likes	Dislikes
algorithms	Medium (50.43%)	2565	78

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.

Notes

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Solution

Here we use tree.
Each node subtracts the elements of the array until the value of node is lower than 0.

Reduce redundant.(the subtracts of lower node is large or equal to lower node)

Code


# @lc app=leetcode id=39 lang=python

# [39] Combination Sum


# @lc code=start
class (object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        len_target = len(candidates)
        res = []
        def find_sum(start,list_now,target_now):
            if(target_now == 0):
                res.append(list_now[:])
            else:
                for i in range(start,len_target):
                    if(target_now - candidates[i]<0):
                        continue
                    else:
                        list_now.append(candidates[i])
                        find_sum(i,list_now,target_now - candidates[i])
                        list_now.pop()
        find_sum(0,[],target)
        return res

Result

Accepted
168/168 cases passed (48 ms)
Your runtime beats 72.65 % of python submissions
Your memory usage beats 59.18 % of python submissions (11.8 MB)