Algorithms with Selection Pattern

This post focusses on a particular type of recursive problem, SELECTION! This is one of the most commonly occurring recursions (and Dynamic Programming) pattern. The post will discuss some of the famous problems of this category and what’s the approach to solve them.

In Selection pattern, we find all combinations of the given input that match certain criteria. As the name suggests we simply include/exclude, or select, each item in our input list and add to the (potential) response list. Finding out all the combinations (which satisfy the given criteria) is the core of the selection problem.

Subset Problem

Generate all combinations of an input string, all characters being unique (like “ABC”, “xyz” etc).

public static void combination(String input){
    combination(input, "");
}
private static void combination(String input, String result){
    if(input.isEmpty()){
        System.out.println(result);
        return;
    }
    char ch = input.charAt(0);

    // Exclude the first char in the result
    String excludeCh = result;
    combination(input.substring(1),excludeCh);

    // Include the first char in the result
    String includeCh = result+ch;
    combination(input.substring(1),includeCh);
}
combination("ABC");  

Output:

C
B
BC
A
AC
AB
ABC

Now, what if we had array instead of String. Essentially, the approach is the same. Please note that below implementation also generates the response (unlike the previous one which just wrote output on console)

public static List<List<Integer>> combinations(int[] n) {
    List<List<Integer>> results = new LinkedList();
    combinations(n, 0, results, new LinkedList<Integer>());
    return results;
}

private static void combinations(int[] n, int i, List<List<Integer>> results, List<Integer> path) {
    if (i == n.length) {
        results.add(path);
        System.out.println(path);
        return;
    }
    // Find all the combinations that exclude the current item
    combinations(n, i+1, results, path);
    
    // Find all the combinations that include the current item
    List<Integer> pathWithCurrent = new LinkedList(path);
    pathWithCurrent.add(n[i]);
    combinations(n, i+1, results, pathWithCurrent);
}
int[] input = {1, 2, 3};
Subsets.combinations(input);

Graphical Representation of Recursion

Print all 3 combinations of entries from an array. Brute force approach is- run 3 loops (i,j,k) and select all possible combinations of entries from the array. Complexity is O(N³). This is the same as nC3.

Generate all combinations is the same as generating a subset of a set or power set of a set. Complexity will be nC0+nC1+nC2….+nCn = O(2^n)

Wondering why are we creating a new array, pathWithCurrent? Each recursive call should have its own version of the included list else all elements will get included in the same list. Each call should return a value (not necessarily though) and then next call should be decided based on that.

Combination Sum Problems

Given an infinite number of quarters(25 cents), dimes(10 cents), nickels(5 cents), and pennies(1 cent). Write code to calculate the number of ways of representing n cents.

public static List<List<Integer>> combinationSum(int[] coins, int target){
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> oneCombination = new ArrayList<>();
    int startIndex=0;
    combinationSum(coins, target, startIndex, result, oneCombination);
    return result;
}

private static void combinationSum(int[] coins, int target, int index, List<List<Integer>> result, List<Integer> comb){
    if(target < 0) return;    // REJECT

    if(target == 0){   //ACCEPT
        System.out.println(comb);
        result.add(comb);
        return;
    }

    for(int i=index; i<coins.length; i++){  //STEP
        comb.add(coins[i]);
        combinationSum(coins, target-coins[i], i, result, comb);
        comb.remove(comb.size()-1);
    }
}
int[] cents = {2,5,10,25};
combinationSum(cents, 10);

Output:

[2, 2, 2, 2, 2]
[5, 5]
[10]

Now, what if the problem was to find only unique combinations. Only the third one should be output. To, allow duplicates we are NOT incrementing the value of i in successive recursive calls.

Above is an example of finding all possible solutions for a problem. There is a variation of backtracking problem which stops once it encountered ANY solution. Like finding any path in a maze. But, if you want to find the shortest path in a maze then we need to find all possible paths with dynamic reject (i.e. if the current path has exceeded the best case so far).

Knapsack Problem

In this problem, we have a series of items that have weights and values. We want to figure out what the maximum value is that we can achieve while remaining under some fixed weight. Many people recognize this as a dynamic programming problem since it’s a classic example, but let’s look at it from a recursive standpoint.

// W: knapsack capacity
public static int knapSack(int[] v, int[] w, int n, int W) {
    if (W < 0) {   // base case: Negative capacity
        return Integer.MIN_VALUE;
    }

    // base case: no items left or capacity becomes 0
    if (n < 0 || W == 0) {
        return 0;
    }

    // Case 1. include current item n in knapSack (v[n]) and recurse 
    // for remaining items (n - 1) with decreased capacity(W - w[n])
    int include = v[n] + knapSack(v, w, n - 1, W - w[n]);

    // Case 2. exclude current item n from knapSack and recurse for
    // remaining items (n - 1)
    int exclude = knapSack(v, w, n - 1, W);

    // return maximum value we get by including/excluding current
    return Integer.max(include, exclude);
}
int[] weight = {1,2,3};
int[] val = {6,10,12};
int result = knapSack(val, weight, 2, 5);