C# DFS Solution (Beats 92%)


  • 0
    K

    We sort the array first so that we can handle duplicates easily. We want to avoid situations where we use the same number but in different indices the same amount of times. This is because we don't want duplicate answers in our solution. So, when we encounter duplicate numbers, we want to use them 0 to n times, where n is the number of duplicates. The trick is that in the stack frame where we choose to skip using a duplicate number, we fast forward the index to where the duplicate numbers end.

    public class Solution {
        public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
            Array.Sort(candidates);
            IList<IList<int>> list = new List<IList<int>>();
            Helper(list, new List<int>(), candidates, target, 0);
            return list;
        }
        
        private void Helper(IList<IList<int>> list, IList<int> currList, int[] candidates, int target, int index) {
            if(target == 0) {
                list.Add(new List<int>(currList));
                return;
            }
            
            if(index >= candidates.Length || target < 0) {
                return;
            }
    
            currList.Add(candidates[index]);
            Helper(list, currList, candidates, target - candidates[index], index + 1);
            currList.RemoveAt(currList.Count - 1);
            
            index++;
            while(index < candidates.Length && candidates[index] == candidates[index - 1]){
                index++;
            }
            
            Helper(list, currList, candidates, target, index);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.