C# - recursive backtracking with trimming optimization


  • 0

    essentially same as others with slight trimming optimization for breaking for loop early when sum is going to be too large. Not just compare that the next number added to the set will exceed the sum but actually checking that the how ever many numbers remain to be added will not exceed the set. Since the numbers added are increasing we can check that ("number or elements remaining" x "number to be added") < "remaining sum"

    if (currSum + i*(k-curr.Count) > n) break;
    
        public IList<IList<int>> CombinationSum3(int k, int n) 
        {
            IList<IList<int>> lists = new List<IList<int>>();
            Helper(k, n, 1, new List<int>(), 0, lists);
            return lists;
        }
        
        public void Helper(int k, int n, int start, IList<int> curr, int currSum, IList<IList<int>> lists)
        {
            if (curr.Count == k)
            {
                if (currSum == n)
                {
                    lists.Add(new List<int>(curr));
                }
                return;
            }
            
            for (int i = start; i <= 9; i++)
            {
                // trimming
                if (currSum + i*(k-curr.Count) > n) break;
                
                curr.Add(i);
                Helper(k, n, i + 1, curr, currSum + i, lists);
                curr.RemoveAt(curr.Count - 1);
            }
        }
    

Log in to reply
 

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