LeetCode: 40. Combination Sum II

LeetCode: 40. Combination Sum II

Problem: 40. Combination Sum II

Link: https://leetcode.com/problems/combination-sum-ii/

Difficulty: Medium

Description:

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

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

Note:

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

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:

[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6] ]

Example 2:

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

[[1,2,2],[5] ]

Solution:

Language: Swift

Runtime: 24ms
Memory: 18.8MB

Copy to Clipboard

class Solution {
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result = [[Int]]()
        var combination = [Int]()
        
        backtrack(0, target, candidates.sorted(), &combination, &result)
        
        return result
    }
    
    func backtrack(_ start: Int, _ target: Int, _ nums: [Int], _ combination: inout [Int], _ result: inout [[Int]]) {
        if target == 0 {
            result.append(combination)
        } else {
            for i in start ..< nums.count where nums[i] <= target {
                if nums[i] > target {
                    break
                }
                
                if i > start && nums[i] == nums[i - 1] {
                    continue
                }
                ////try current number
                combination.append(nums[i])
                backtrack(i + 1, target - nums[i], nums, &combination, &result)
                //remove the last wrong number
                combination.removeLast()
            }    
        }
    }
}

Related Posts

Leave A Comment Cancel reply