Find all combinations of an array and get top k sum elements

Question

I have an array of numbers say [1,2,3,1,1000] , now I want to get all possible combinations of this array and calculate its sum. Combinations are valid such that two combinations have different subset of elements. Then order all the sum values in descending order and get the top k elements.

Example:

[1,2,3,1,1000]

Combinations:

Duplicates of earlier ones are striked out, for example (3,1) matches the earlier (1,3).

(), (1), (2), (3), (1), (1000), (1,2), (1,3), (1,1), (1,1000), (2,3), (2,1), (2,1000), (3,1), (3,1000), (1,1000), (1,2,3), (1,2,1), (1,2,1000), (1,3,1), (1,3,1000), (1,1,1000), (2,3,1), (2,3,1000), (2,1,1000), (3,1,1000), (1,2,3,1), (1,2,3,1000), (1,2,1,1000), (1,3,1,1000), (2,3,1,1000), (1,2,3,1,1000)

And the corresponding sums:

0, 1, 2, 3, 1, 1000, 3, 4, 2, 1001, 5, 3, 1002, 4, 1003, 1001, 6, 4, 1003, 5, 1004, 1002, 6, 1005, 1003, 1004, 7, 1006, 1004, 1005, 1006, 1007

Getting top k=3, sums = 1007, 1006, 1005

So output is [1007, 1006, 1005].

Constraints:

• Array size n = 1 to 10⁵
• Array elements -10⁹ to 10⁹
• k ranges from 1 to 2000

This is my code, reference taken from here:

static List<Long> printDistSum(int arr[]) {
        List<Long> list = new ArrayList<>();
        int n = arr.length;
        // There are totoal 2^n subsets
        long total = (long) Math.pow(2, n);
        
        // Consider all numbers from 0 to 2^n - 1
        for (int i = 0; i < total; i++) {
            long sum = 0;

            // Consider binary representation of
            // current i to decide which elements
            // to pick.
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) != 0)
                    sum += arr[j];

            // Print sum of picked elements.
            list.add(sum);
        }
        return list;
    }

This code works for small range of inputs but times out for large range of inputs. How to solve this program.

Answer 1

I was also asked the same question yesterday but sadly I was not able to solve it yesterday. I have tried solving it today and think I have the answer today.

First of all I don't think that different subsets mean different costs in a set i.e in array of [1,2,3,1] both subsets are valid => [1,2,3] and [2,3,1] as they both use different 1's. Now here is my solution keeping this in mind. But if you really want to keep distinct elements in set then you can simply remove the multiple elements and do partial_sort then.

Logic

1. Store sum of all +ve nos. in a variable, say maxsum.
2. Convert the negative nos. to their absolute values.
3. Get lowest min(k-1, n) elements in sorted order.
4. Find all their combinations and subtract them from the maxsum.
5. While finding all their combinations we only need lowest k-1 combos. So we have to find a way to keep the number of combinations to that. For that use a sorted data structure and limit its size to k and then for every element in the sorted array iterate through the combos and add those combos to the sorted data structure if the end element of that data structure is greater. Also pop the end element after that.
6. For taking care of the above point I am using 2 vectors since the order already remains sorted.

The proposed solution has time complexity of O(n*log(k) + k^2).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int ll;

template <class T>
void print(vector<T> topSumm)
{
  for (ll itr : topSumm)
    cout << itr << '\t';
  cout << '\n';
}

vector<ll> mergeSortedArrays(vector<ll> &minns, vector<ll> &temp)
{
  vector<ll> ans(minns.size() + temp.size());
  int i{0}, j{0}, k{0};
  while (i < minns.size() && j < temp.size())
  {
    if (temp[j] < minns[i])
      ans[k++] = temp[j++];
    else
      ans[k++] = minns[i++];
  }
  while (i < minns.size())
    ans[k++] = minns[i++];
  while (j < temp.size())
    ans[k++] = temp[j++];
  return ans;
}

vector<ll> topKSum(vector<int> &arr, int k)
{
  int n{(int)arr.size()};
  ll maxSumm{0};
  for (int i{0}; i < n; ++i)
  {
    if (arr[i] > 0)
      maxSumm += arr[i];
    else
      arr[i] = -arr[i];
  }
  int nk{min(k - 1, n)};
  partial_sort(arr.begin(), arr.begin() + nk, arr.end());
  vector<ll> minns{0, maxSumm};
  ll summ{};
  bool breakOuter{false};
  for (int i{0}; i < nk; ++i)
  {
    vector<ll> temp;
    for (ll nums : minns)
    {
      summ = nums + arr[i];
      if (minns.size() + temp.size() < k)
        temp.push_back(summ);
      else
      {
        if (minns.back() > summ)
        {
          minns.pop_back();
          temp.push_back(summ);
        }
        else
        {
          if (nums == 0)
            breakOuter = true;
          break;
        }
      }
    }
    if (breakOuter)
      break;
    minns = mergeSortedArrays(minns, temp);
  }
  vector<ll> ans(k);
  int i{0};
  for (ll nums : minns)
    ans[i++] = maxSumm - nums;
  return ans;
}

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    ll maxSumm{0};
    for (int i{0}; i < n; ++i)
      cin >> arr[i];
    vector<ll> topSums = topKSum(arr, k);
    print<ll>(topSums);
  }
  return 0;
}

Answer 2

Pls ignore all previous posts cuz they are all wrong. Intuitively, we gotta use backtrack to find all desired combos, but it's impossible to backtrack on 10^5 elements.

Constraint 1 <= n <= 10^5 alludes that our algorithm bottlenecked by O(nlogn) sorting

Constraint 1 <= k <= min(2000,2^n) alludes that we can backtrack on k elements since k is less than 11. 2^11=2024/log(2000)=11 -- actually this "2^n" gives away solution :)

My algorithm (nlog(n) + 2^k)

1. sort the array
2. Record the highest score combo which is the sum of all positive integers
3. Find a window in the sorted array of math.min(log(k)--which is less than 11,n) elements -- worst case, this window consists of the lowest 11 absolute values in the sorted array. Several approaches to achieve that, since the candidates must be inside 22 elements window(11 smallest positive values + 11 biggest negative values), we can use PriorityQueue of size 11 scanning over these 22 elements. or we can use two pointers to find the sliding window of size 11.
4. backtrack on this 11 absolute value elements window, find sum of each combo and put them into a size k/k-1 PriorityQueue. (k is for the case that there's no positive elements)
5. result is the sum of all positive integers plus (sum deducted by each of k-1 elements in PriorityQueue).

Answer 3

I probably have solution that should be good enough. It has time complexity O(n * k * log(k)).

First we need to calculate max sum - sum of all positive values.

Next we need to iterate over positive values, from smallest to largest. For each of these values we calculate sums of new combinations (at the start we have one combination with max sum). New combinations will not contains given value so we need to substract it from sum.

At the end we need to iterate over negative values. These values are not belongs to combinations from previous step so we need to add these values to sums.

In every iteration are needed only k maximum sums. I used the PriorityQueue to store these sums. That class use heap data structure so adding/removing values has logarithmic time.

Code:

private static long[] findSums(int[] array, int k) {
    long maxSum = Arrays.stream(array).filter(it -> it >= 0).sum();

    int[] positives = Arrays.stream(array).filter(it -> it >= 0).sorted().toArray();
    int[] negatives = Arrays.stream(array).filter(it -> it < 0).sorted().toArray();
    // sort time complexity is O(n*log(n))

    PriorityQueue<Long> sums = new PriorityQueue<>(k); // priority queue is implemented using heap so adding element has time complexity O(log(n))
    sums.add(maxSum); // we start with max sum - combination of all positive elements

    int previous = Integer.MIN_VALUE;
    Long[] previousAddedSums = {};
    Long[] sumsToIterate;

    // iterate over positive values
    for (int i = 0; i < positives.length; i++) {
        if (positives[i] == previous) {
            sumsToIterate = previousAddedSums;
        } else {
            sumsToIterate = sums.toArray(new Long[sums.size()]);
        }
        previousAddedSums = new Long[sumsToIterate.length];
        for (int j = 0; j < sumsToIterate.length; j++) {
            long newSum = sumsToIterate[j] - positives[i];
            // new sum is calculated - value positives[i] is removed from combination (subtracted from sum of that combination)
            sums.add(newSum);
            previousAddedSums[j] = newSum;
            if (sums.size() > k) {
                sums.poll(); // only first k maximum sums are needed at the moment
            }
        }
        previous = positives[i];
    }

    previous = Integer.MAX_VALUE;
    // iterate over negative values in reverse order
    for (int i = negatives.length - 1; i >= 0; i--) {
        if (negatives[i] == previous) {
            sumsToIterate = previousAddedSums;
        } else {
            sumsToIterate = sums.toArray(new Long[sums.size()]);
        }
        previousAddedSums = new Long[sumsToIterate.length];
        for (int j = 0; j < sumsToIterate.length; j++) {
            long newSum = sumsToIterate[j] + negatives[i]; // value negatives[i] is added to combination (added to sum of that combination)
            sums.add(newSum);
            previousAddedSums[j] = newSum;
            if (sums.size() > k) {
                sums.poll();
            }
        }
        previous = negatives[i];
    }

    long[] result = new long[sums.size()];
    for (int i = sums.size() - 1; i >=0 ; i--) {
        result[i] = sums.poll();
    }
    // get sums from priority queue in proper order
    return result;

    // this whole method has time complexity O(n * k * log(k))
    // k is less than or equal 2000 so it should be good enough ;)
}

Demo: https://ideone.com/yf6POI

Edit: I have fixed my solution. Instead of iterating over distinct values I check if current value is same like previous. In that case I use combinations (sums) created in previous step. This prevents from creating duplicates of combinations.

I'm sorry if I didn't explain this well enough. I don't have experience in describing algorithmic / mathematical things in english.