[Solved] Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination.

Machine Learning Projects

Table of Contents

Question

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Python Solution

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        combinations = []
        candidates.sort()
        
        def solve(ind=0,curr_sum=0,curr_list=[]):
            if curr_sum==target:
                if curr_list not in combinations:
                    combinations.append(curr_list[:])
                return
            
            for i in range(ind,len(candidates)):
                if candidates[i]+curr_sum>target:
                    break
                solve(i+1,candidates[i]+curr_sum,curr_list+[candidates[i]])
        solve()
        return combinations

Leave a Comment

Your email address will not be published.