[LeetCode] Combination Sum II

Problem: 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:

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

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

Approach: Its a typical backtracking problem except we need to take care of the duplicates too. We can take care of duplicates by sorting the array "candidates".

Implementation in C#:

    public IList<IList<int>> CombinationSum2(int[] candidates, int target)

    {

        List<IList<int>> result = new List<IList<int>>();

        Array.Sort(candidates);

        List<int> currCandidates = new List<int>();

        this.CombinationSum2Rec(candidates,

                            0,

                            target,

                            0,

                            currCandidates,

                            result);

        return result;

    }

    private void CombinationSum2Rec(int[] candidates,

                                int currIndex,

                                int target,

                                int currSum,

                                List<int> currCandidates,

                                List<IList<int>> result)

    {

        if (currSum == target)

        {

            result.Add(new List<int>(currCandidates));

            return;

        }

        for (int i = currIndex; i < candidates.Length; ++i)

        {

            if (currSum + candidates[i] > target)

            {

                break;

            }

            if (i > currIndex && candidates[i] ==  candidates[i - 1])

            {

                continue;

            }

            currCandidates.Add(candidates[i]);

            this.CombinationSum2Rec(candidates,

                                i + 1,

                                target,

                                currSum + candidates[i],

                                currCandidates,

                                result);

            currCandidates.RemoveAt(currCandidates.Count - 1);

        }

    }

Complexity: O(2^n)