Problem link -  CSES - Apple Division

Algorithm(s) - Complete Search with Subsets, Complete Search with Recursion

Time complexity  - O(2ⁿ)

more Information - Complete Search with Recursion · USACO Guide

Short Editorial

Generate all possible subsets of apples and calculate the difference in weights of apples that are in the subset and the ones that are not.

Detailed Editorial

There are n (n <= 20) apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

This problem can be solved by generating all possible subsets and calculating the difference in weights of apples that are in the subset and the ones that are not. The answer is the minimum of these differences.

There are 2 ways of generating all possible subsets. 

1. Using recursion

2. Using bitmasks

Please note that generating subsets is much more efficient than generating permutations. We do not need permutations since order of apples in the groups is not important, only the total weight of the groups is important. 

1. Using recursion 

In this solution, we define a function that takes 3 arguments, number of apples, weight of group 1 and weight of group 2 and returns an integer. If the first parameter is same as the number of apples, the function returns the difference between the weights of the groups. If the value of the first parameter is less than number of apples, it recursively calls itself 2 times, first by adding the next apple to group 1 and then by adding the same apple to group 2 and then returns the minimum of the return values of these function calls as the return values.

The recursion starts by calling the function with base case (all parameters as 0) since we will be starting with empty groups with 0 weights.

Line by line editorial

long long diff(int i, long long w1, long long w2){

Recursive function with 3 parameters (number of apples, weight of group 1, weight of group 2).

    if(i==n)

        return abs(w1-w2);

Exit condition for the recursive call. The recursion will stop when number of apples added to the two groups equals the total number of apples to be divided

        return min(diff(i+1,w1+weights[i],w2),diff(i+1,w1,w2+weights[i]));    

Recursive call in case i < n. In this call, function calls itself 2 times. In first call, i^th apple is added to group 1 and in second call it is added to group 2. The line returns minimum of the return values of these two recursive calls.

This recursive call will generate all the possible subsets and will always choose the most optimum subset that has the lowest weight between the two groups.

    cout << diff(0,0,0) << '\n';

Initial call the recursive function with base case parameters. Base case is an empty groups of apple with 0 weights.

Complete Code (Recursion)

#include<bits/stdc++.h>

using namespace std;

int n;

int weights[20];

long long diff(int i, long long w1, long long w2){

    if(i==n)

        return abs(w1-w2);

    else

        return min(diff(i+1,w1+weights[i],w2),diff(i+1,w1,w2+weights[i]));    

}

 

int main(){

    cin >> n;

    for(int i=0;i<n;i++) cin >> weights[i];

    cout << diff(0,0,0) << '\n';

}

2. Using Bitmasks

Another efficient way to generate subsets is using bit representation of integers. This technique can be used to generate subsets when size of the set is less than or equal to 32 since an int in c++ has a size of 4 bytes or 32 bits. We can also use long long but the resulting number of subsets will be too large and will not fir time limit of most competitions.

Each bit of the integer can either be 0 or 1 indicating if the corresponding item in the set is part of the subset (bit = 1) or not (bit = 0). First item of the set is represented by the rightmost bit of the number, second item of the set is represented by second bit from right and so on.

To solve this problem, we generate all possible subsets and then calculate weight of apples in the subset and weight of apples not in the subset. We can then calculate the difference between the two. Final answer will be the minimum of these differences values.

Line by line editorial

    for(int b = 0; b < (1 << n); b++){

A loop that goes over all the subsets. A set of size n will have  2ⁿ  subsets. We use the left shift operator to get the value of  2ⁿ  i.e. 1 << n = 2ⁿ 

            if(b & (1 << i)){

Check if an apple belongs to the subset. Binary and (&) operator is used to check if apple at index i in the set is part of the subset represented by integer b.

Complete Code (Bitmask)

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n;

    cin >> n;

    vector<int> weights(n);

    vector<long long> subset_weights(1 << n);

    long long total_weight = 0;

    for(int i = 0; i < n; i++){

        cin >> weights[i];

        total_weight += weights[i];

    }

    long long ans = LONG_MAX;

    for(int b = 0; b < (1 << n); b++){

        long long w1 = 0;

        for(int i = 0; i < n; i++){

            if(b & (1 << i)){

                w1 += weights[i];

            }

        }

        long long w2 = total_weight - w1;

        ans = min(ans, abs(w1-w2));

    }

    cout << ans << endl;

    return 0;

}

Problem link -  Four Sum | CodeChef

Algorithm(s) - 3 pointer method

Time complexity  - O(N²)

Short Editorial

Create a pair of 2 pointers where each pair calculates frequency of sum of the 2 numbers pointed to by the pointers. 

Detailed Editorial

In this problem, we are given a set of numbers (N <= 5000) and we are asked to find number of ways of selecting 4 numbers whose sum equals a given number T (<= 10⁶).

A brute force algorithm using 4 pointers can be used to solve this problem in O(N⁴) time but that will not fit the time limit. Given the size of N, we need an O(N²) algorithm.

To solve this problem, we set up three pointers (i,j,k). Pointer i iterates from 1 to n-1, pointer j iterates from i+1 to n-1 and pointer k iterates from 0 to i-1.

Pointers i & j are used to calculate sum of 2 numbers pointed to by these pointers and pointers i & k are used to calculate sum of two numbers pointed to by these 2 pointers. However, pointer i in these pairs will not be pointing to the same number as it would have moved by one position to right before it will be used so using these 3 pointers we will be able to calculate sum of 4 numbers.

While we iterate over the input array, we will maintain an auxiliary array called frequency that will store the number of ways of forming a sum pointed to by the two pointers.

Line by line Editorial

    for(int i = 1; i < n; i++){

        for(int j = i+1; j < n; j++){

Two nested loop for 2 pointers i & j as described above.

            ans += freq[t-nums[i]-nums[j]]; 

Since pointers i & j are pointing to two numbers, we can get sum of these two numbers. We need to find the number of ways of generating the remaining sum which will be stored in the freq array which is updated in the later part of the code.

        for(int k = 0; k < i; k++){

Loop for the 3rd pointer. This loop is nested inside the loop for i poiner.

            freq[nums[i]+nums[k]]++;

Pointers i & k are pointing to two numbers. This line updates the freq array to increment number of ways of forming a sum of two numbers pointed by these 2 numbers by one.

Note that since loop for pointer k starts after loop for pointer j ends, the next iteration of loop j will use the next value of pointer i and not the same value of i that will be used by the loop for pointer k. This will ensure that two nested loops (i & j and i & k) use separate values of i, thus pointing a sum of 4 values and not 3. 

Complete Code

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n, t;

    cin >> n >> t;

    vector<int> nums(n), freq(t+1);

    for(int i = 0; i < n; i++)

        cin>>nums[i];

    sort(nums.begin(), nums.end());

    long long ans = 0;

    for(int i = 1; i < n; i++){

        for(int j = i+1; j < n; j++){

            if(nums[i]+nums[j] > t)

                break;

            ans += freq[t-nums[i]-nums[j]];

        }

        for(int k = 0; k < i; k++){

            if(nums[i]+nums[k] > t)

                break;

            freq[nums[i]+nums[k]]++;

        }

    }

    cout<<ans;

}