C# backtrack Ksum implemtnation


  • 0
    C

    C# backtrack Ksum implemtnation

          public IList<IList<int>> FourSum(int[] nums, int target)
          {
                List<IList<int>> res = new List<IList<int>>();
                if (nums.Length < 4)
                {
                    return res;
                }
    
                Array.Sort(nums);
                KSum(res, new List<int>(), nums, target, 4, 0, nums.Length - 1);
                return res;
            }
    
            private void KSum(IList<IList<int>> res, IList<int> cur, int[] nums, int target, int k, int start, int end)
            {
                if (k == 0 || start > end)
                {
                    return;
                }
    
                if (k == 1)
                {
                    for (int i = start; i <= end; i++)
                    {
                        if (nums[i] == target)
                        {
                            cur.Add(nums[i]);
                            res.Add(new List<int>(cur));
                            return;
                        }
                    }
                }
    
                if (k == 2)    // 2 sum
                {
                    while (start < end)
                    {
                        int sum = nums[start] + nums[end];
    
                        if (sum == target)
                        {
                            cur.Add(nums[start]);
                            cur.Add(nums[end]);
                            res.Add(new List<int>(cur));
                            cur.RemoveAt(cur.Count - 1);
                            cur.RemoveAt(cur.Count - 1);
    
                            // avoid duplicate
                            while (start < end && nums[start] == nums[start + 1])
                            {
                                start++;
                            }
    
                            start++;
    
                            while (start < end && nums[end] == nums[end - 1])
                            {
                                end--;
                            }
    
                            end--;
                        }
                        else if (sum < target)
                        {
                            while (start < end && nums[start] == nums[start + 1])
                            {
                                start++;
                            }
    
                            start++;
                        }
                        else
                        {
                            while (start < end && nums[end] == nums[end - 1])
                            {
                                end--;
                            }
    
                            end--;
                        }
    
                    }
    
                    return;
                }
    
                // pruning
                if (k * nums[start] > target || k * nums[end] < target)
                {
                    return;
                }
    
                // k > 2: choose nums[i] and do k-1 sum on the rest of right
                for (int i = start; i <= (end - k + 1); i++)
                {
                    // avoid dupicate
                    if (i > start && nums[i] == nums[i - 1])
                    {
                        continue;
                    }
    
                    if (k * nums[i] <= target)
                    {
                        cur.Add(nums[i]);
                        KSum(res, cur, nums, target - nums[i], k - 1, i + 1, end);
                        cur.RemoveAt(cur.Count - 1);
                    }
                }
            }
    

Log in to reply
 

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