C# - recursive with backtracking


  • 0

    this is the same as others, the one difference is the way I handle avoiding duplicates. Most of the solutions avoid them before the recursion with some logic like "if this is not the first of the dupes then skip to next unique number". I just do the recursion first then skip the dupes after that. Same more or less

        public IList<IList<int>> CombinationSum2(int[] candidates, int target) 
        {
            Array.Sort(candidates);
            IList<IList<int>> lists = new List<IList<int>>();
            Find(lists, candidates, target, 0, new List<int>());
            return lists;
        }
        
        public void Find(IList<IList<int>> lists, int[] arr, int target, int start, IList<int> curr)
        {
            if (target == 0)
            {
                lists.Add(new List<int>(curr));
                return;
            }
            
            for (int i = start; i < arr.Length; i++)
            {
                if (arr[i] > target)
                {
                    break;
                }
                curr.Add(arr[i]);
                Find(lists, arr, target - arr[i], i + 1, curr);
                curr.RemoveAt(curr.Count - 1);
                
                // avoid duplicate lists
                while (i < arr.Length - 1 && arr[i+1] == arr[i])
                {
                    i++;
                }
            }
        }
    

Log in to reply
 

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