[AirBnb] Combination Sum

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

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Approach: Use backtracking.

Implementation in C#:

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

        {

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

            if (candidates == null || candidates.Length == 0)

            {

                return result;

            }

            Array.Sort(candidates);

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

            this.FindCombinationSumCandidates(candidates, target, result, currResult, 0);

            return result;

        }

        private void FindCombinationSumCandidates(int[] candidates, int target, IList<IList<int>> result, List<int> currResult, int currIndex)

        {

            if (target < 0)

            {

                return;

            }

            if (target == 0)

            {

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

                return;

            }

            while(currIndex < candidates.Length && target - candidates[currIndex] >= 0)

            {

                currResult.Add(candidates[currIndex]);

                this.FindCombinationSumCandidates(candidates, target - candidates[currIndex], result, currResult, currIndex);

                ++currIndex;

                currResult.RemoveAt(currResult.Count - 1);

            }

        }

Complexity: O(2 ^ k) where k is is the sum of target / candidates[i] for all i = 0 to length of candidates.