I was interviewing for one of the big techs where I was asked a programming question in the problem solving round. The question is very similar to the Two Sum problem in Leet Code except for one tricky constraint. The question goes like this : Given an array of integers nums, an integer target and an integer limit, return exactly one set of elements that counts up to the given limit and adds up to the given target.

 Input: nums = [2,7,11,15], target = 20, limit = 3
 
 Output: [2, 7, 11]

Explanation : The target is 20 and the limit is 3, so, we will have to find 3 numbers from the array that add up to 20.

I wasn't able to solve this during the interview and have been searching for a solution ever since. The brute force approach is to run as many loops as the limit, which is not viable, considering the fact that the limit may be <= 10,000

And another is to extract sub-arrays of length = limit, run through each and every one, add their elements and return a sub-array that adds up to Target.

But, I am sure there must be a more efficient approach to solve this. Any ideas?

Edit :

The output that we return may be random and not necessarily contiguous.

The limit has to be met and the number of elements that we return must be equal to the limit.

There is no limit on the size of the array

CodePudding user response：

Use Stack (recursively) to find the array elements which will sum to the desired target within the required array elements limit. Doing it this way will actually find all combinations but only those which use fall on the elements limit are placed into a List.

Please read the comments in code. Delete them later if you like. Here is a runnable to demonstrate this process:

package sumtargetlimit_demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;


public class SumTargetLimit_Demo {

    // The desired Target Sum
    private int targetSum = 20;
    
    /* The max allowable array elements to use in order to acquire 
       the desired Target Sum.    */
    private int numbersLimit = 3;
    
    // A Stack to hold the Array elements which sum to the desired Target Sum.
    private Stack<Integer> stack = new Stack<>();

    // Store the summation of current elements held in stack.
    private int sumInStack = 0;
    
    /* A List Interface of Integer[] array to hold all the 
       combinations of array elements which sum to target. */
    private List<Integer[]> combinationsList = new ArrayList<>();
    
    
    public static void main(String[] args) {
        // Demo started this way to avoid the need for statics.
        new SumTargetLimit_Demo().startDemo(args);
    }
    
    private void startDemo(String[] args) {
        // The int array to work against.
        int[] intData = {2, 7, 11, 15};
        
        /* See which array elements can acquire the desired 
           Target Sum with the maximum number of array elements 
           specified in the numbersLimit member variable.     */
        getSummations(intData, 0, intData.length);
        
        // Display the found results to Console window...
        if (combinationsList.isEmpty()) {
            System.err.println("No integer elements within the supplied Array will");
            System.err.println("provide a Taget Sum of "   targetSum   " with a maximum number");
            System.err.println("limit of "   numbersLimit   ".");
        }
        else {
            for (Integer[] intArray : combinationsList) {
                System.out.println(Arrays.toString(intArray).replaceAll("[\\[\\]]", ""));
            }
        }
    }
    
    // Note: This method is recursive...
    public void getSummations(int[] data, int startIndex, int endIndex) {
        /* Check to see if the sum of array elements stored in the
           Stack is equal to the desired Target Sum. If it is then 
           convert the array elements in the Stack to an Integer[] 
           Array and add it to the conmbinationsList List.       */
        if (sumInStack == targetSum) {
            if (stack.size() <= numbersLimit) {
                combinationsList.add(stack.toArray(new Integer[stack.size()]));
            }
        }

        for (int currIndex = startIndex; currIndex < endIndex; currIndex  ) {
            if (sumInStack   data[currIndex] <= targetSum) {
                stack.push(data[currIndex]);
                sumInStack  = data[currIndex];

                // Make the currentIndex  1, and then use recursion to carry on.
                getSummations(data, currIndex   1, endIndex);
                sumInStack -= stack.pop();
            }
        }
    }
    
}

Try a much larger int[] array and play with the Target Sum and Number Limit to see how things work.

CodePudding user response：

Another way, to look at this problem is through the eyes of dynamic programming. For any element in the array, there are two cases:

1. It will be a part of the elements, which make up the sum, in that case, we recursively, find the elements that make the remaining sum, with limit - 1.
2. It will not be part of the elements, which make up the sum, in this case, we look for the target, in the remaining part of the array.

Here, is the sample following the above logic:

import java.util.*;
class HelloWorld {
    static Map<Integer, List<Integer>> cache = new HashMap<>();
    public static void main(String[] args) {
        int[] array = {9, 2, 15, 11, 7, 23, 54, 50, 12};
        int limit = 4;
        int target = 35;
        // This is to optimize the search for element in case the limit is 1
        Arrays.sort(array);
        List<Integer> subarray = getElementsWithSumEqualToTarget(array, 0, limit, target);
        System.out.println(subarray);
    }
    static List<Integer> getElementsWithSumEqualToTarget(int[] array, int startingIndex, int limit, int target) {
         // If limit is 0, or we have reached the end of the array then sum doesn't exists.
        if(limit == 0 || startingIndex >= array.length) {
            return null;
        } else if(limit == 1) {
            // For limit 1, we can do a simple binary search, or linear search in that case Arrays.sort can be removed
            int index = Arrays.binarySearch(array, startingIndex, array.length - 1, target);
            if(index < 0) {
                return null;
            }
            ArrayList<Integer> list = new ArrayList();
            list.add(target);
            return list;
        } else if (cache.containsKey(target)) {
          // If for a given sum, the subarray of elements, is already present, we can return it from the cache.(Memoization) 
            return cache.get(target);
        }
        // Case 1: The current element will be part of the sum.
        List<Integer> subarray = getElementsWithSumEqualToTarget(array, startingIndex   1, limit - 1, target - array[startingIndex]);
        if(subarray != null) {
            subarray.add(array[startingIndex]);
            // Add target and subarray to the cache
            cache.put(target, subarray);
            return subarray;
        }
        // Case 2: Current element is not part of the sum
        subarray = getElementsWithSumEqualToTarget(array, startingIndex   1, limit, target);
        if(subarray != null) {
            cache.put(target, subarray);
        }
        return subarray;
    }
}

Please try it out on large datasets, and see how it works. Hopefully, it helps.