Nico Addai

One type of problem that consistently stumps me when solving LeetCode questions has to do with finding unique sub-arrays of a longer array and then checking something about those sub-arrays. Let’s break down the concept of finding the number of combinations that sum up to a target, also known as the k-sum problem.

To find all unique subarrays of length k within an array, where the subarrays are non-contiguous, you can use a backtracking approach. Here’s the algorithm to achieve this:

Create an empty array result to store the unique subarrays.

Define a recursive function, let’s call it findSubarrays, that takes the following parameters:

• The input array nums.
• The current index start indicating the starting position for the subarray.
• The current subarray subset that is being built.
• The length k of the desired subarrays.

Inside the findSubarrays function:

• If the length of the subset is equal to k, add it to the result array.
• If the length of the subset is greater than k, terminate the current recursive call.
• Iterate from start to the end of the array:
  • Append the current element at index i to the subset.
  • Recursively call findSubarrays with i + 1 as the new start index.
  • Remove the last element from the subset to backtrack and explore other possibilities.

1. Start the recursive call to findSubarrays with the initial parameters: nums, 0 as the start index, and an empty array as the initial subset.
2. Return the result array containing all the unique subarrays of length k within the input array nums.

Here’s how implementation of the algorithm looks in JavaScript:

function findUniqueSubarrays(nums, k) {
  const result = [];

  function findSubarrays(nums, start, subset) {
    if (subset.length === k) {
      result.push([...subset]);
      return;
    }

    if (subset.length > k) {
      return;
    }

    for (let i = start; i < nums.length; i++) {
      subset.push(nums[i]);
      findSubarrays(nums, i + 1, subset);
      subset.pop();
    }
  }

  findSubarrays(nums, 0, []);

  return result;
}

You can call the findUniqueSubarrays function, passing the input array nums and the desired length k, to get all the unique subarrays of length k within the array. The function will return an array containing the subarrays as elements.

The k-sum problem involves finding combinations of k elements from an array such that their sum equals a given target value.

1. The code defines a helper function called kSum, which takes three parameters: nums, target, and k.
2. The function kSum initializes an empty array res to store the resulting combinations that sum up to the target.
3. The function performs some initial checks to determine if it’s possible to obtain a sum of the target value using the remaining elements in the nums array. If it’s not possible, the function returns the empty res array.
4. If k is equal to 2, the function calls another helper function called twoSum. The twoSum function finds pairs of elements in the nums array that sum up to the target value. The result of twoSum is then returned by the kSum function.
5. If k is greater than 2, the function enters a loop that iterates over the nums array.
6. Within the loop, it checks if the current element is the first element or if it’s different from the previous element. This check ensures that duplicate combinations are not generated.
7. For each iteration, the function recursively calls itself (kSum) with the remaining subarray of nums after the current element, the updated target value (subtracting the current element from the original target), and k-1 (since we’ve already used one element).
8. The result of the recursive call is an array of combinations (subsets) that sum up to the updated target value.
9. The function then appends the current element to each combination in subsets to form a valid combination of k elements that sums up to the target.
10. These valid combinations are added to the res array.
11. After the loop completes, the function returns the res array containing all the unique combinations of k elements that sum up to the target.

The code uses a recursive approach to break down the k-sum problem into smaller subproblems. By recursively reducing the problem size and updating the target value, it finds all the valid combinations that satisfy the desired sum.

The twoSum function is a special case of the kSum function when k is equal to 2. It uses the two-pointer technique to efficiently find pairs of elements that sum up to the target value.

Overall, the k-sum problem is solved by iteratively reducing the problem size and leveraging recursion to generate all possible combinations.