Backtracking LeetCode Pattern: Permutations vs Subsets in Java

The basics of backtracking

Backtracking has proven itself to be a universal algorithmic technique that can be applied while solving all kinds of computational problems, from the most primitive (such as counting all possible paths between two vertices) to the most complex ones (such as finding all Hamiltonian paths or solving the N Queen problem).

According to the fundamental study on backtracking, it can be defined as an improvement to the brute force approach. In other words, the basic idea behind the backtracking technique is the search for a solution to a particular problem among all the options available.

The backtracking algorithm owes its success and effectiveness to the depth-first search method. When the algorithm initiates its extensive search for solutions, it promptly applies the abounding function, making it possible to determine whether a proposed solution meets the constraints set. In case the answer is positive, the algorithm continues its search. If this is not the case, the algorithm removes the branch and simply returns to the previous level.

In general, there are three common types of problems that backtracking solves:

Decision problems - finding a feasible solution;
Optimization problems - finding the best solution possible;
Enumeration problems - finding all the feasible solutions.

Now, let's move on from theory to practice and have a look at 2 algo problems solved by the backtracking techniques. Noteworthy is that both of the problems were taken from real job interviews, and they are included in the Leetcode Top Interview Questions list.

Subsets

Problem description

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Input: nums = [0,1,2]

Output: [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]

Idea

It is common knowledge that the power set of a set S is considered to be the set of all subsets of S, including both the empty set and S itself. The power set of {0,1,2} is graphically illustrated below:

The most direct way is to:

compute all the subsets U that do not contain a particular element (which could be any single element);
compute all the subsets V that do contain the required element.

After it, each subset set must appear either inU or in V, providing us with the final result of U⋃V. The construction is recursive, and the base case is when the input set is empty, in which case we return an empty list.

Example

Now, it’s the right moment to study the example:

Let nums = [0,1,2]. Pick any element, e.g., 0.
First, we recursively compute all subsets of {1,2}.
To do this, we select 1. This leaves us with {2}.

Now, we pick 2 and get to the base case. -> {}

Returning from the recursive calls:

3. So, the set of subsets of {2} is {} union with {2}, i.e., {{}, {2}}. 2. The set of subsets of {1, 2} is then {{}, {2}} union with {{1}, {1, 2}}, i.e., {{}, {2}, {1}, {1, 2}}.

The set of subsets of {0,1,2} is then {{}, {2}, {1}, {1, 2}} union with {{0}, {0, 2}, {0, 1}, {0, 1, 2}}, i.e., {{}, {2}, {1}, {1, 2), {0}, {0, 2}, {0, 1}, {0, 1, 2}}.

Solution

class Solution {
  public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new LinkedList<>();
    backtrack(nums, 0, new LinkedList<>(), ans);
    return ans;
  }

  void backtrack(int[] nums, int i, List<Integer> cur, List<List<Integer>> ans){
    ans.add(new ArrayList<>(cur));
    for (int j = i; j<nums.length; j++){
      cur.add(nums[j]);
      backtrack(nums, j + 1, cur, ans);
      cur.remove(cur.size() - 1);
    }
  }
}

Performance

The time complexity: all the subsets are generated and further copied to the output list using O(N×2^N). The number of recursive calls, C(n), satisfies the recurrence C(n) = 2C(n - 1), which solves to C(n) = (2^N). Since we spend O(N) time within a call, the time complexity is O(N×2^N).
The space complexity is calculated by the following formula: O(N). We are using the O(N) space to maintain cur, and are modifying cur in-place with backtracking.

Permutations

Problem description

Given an array nums of distinct integers, return all the possible permutations. The answer can be returned in any order.

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Idea

It is generally known that every permutation of A begins with one of A[0], A[1], ..., A[n-1]. The basic idea here is to generate all permutations starting with A[0], then all permutations starting with A[1], and so on. Computing all permutations starting with A[0] means computing all permutations of A[1:n-1], which suggests the use of recursion.

To compute all permutations starting with A[1], we swap A[0] with A[1] and compute all permutations of the updated A[1:n-1]. As we go on, we restore the original state before embarking on the computation of all permutations that start with A[2], and so on.

Example

For instance, for the array (1, 2, 3), we would first generate all permutations starting with 1.

This implies generating all permutations of (2, 3).
Next, we find all permutations of (2, 3) starting with 2. Given that (3) is an array of length 1, it has the only possible permutation. The implication of this is that (2, 3) has a single permutation starting with 2.
After that, we look for permutations of (2, 3) starting with 3, which can be executed by swapping 2 and 3. Consequently, we will find out that there is a single permutation of (2, 3) starting with 3, namely, (3, 2).

Hence, there are two permutations starting with 1: (1,2,3) and (1,3,2). To find all permutations starting with 2, we swap 1 with 2 and get two permutations again: (2,1,3) and (2,3,1).

The last two permutations we add are (3,2,1) and (3,1,2). In total, there are six permutations: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,2,1) and (3,1,2).

Solution

class Solution {
  List<List<Integer>> result;

  public List<List<Integer>> permute(int[] nums) {
    Arrays.sort(nums);
    result = new ArrayList<>();
    permute(0, nums);
    return result;
   }

   private void permute(int i, int[] nums){
     if (i == nums.length - 1){
       copyToResult(nums);
     }
     for (int j = i; j<nums.length; j++){
       swap(i,j,nums);
       permute(i+1,nums);
       swap(j,i,nums);
     }
   }

  private void copyToResult(int[] nums){
    List<Integer> list = new ArrayList<>();
    for (int num: nums){
      list.add(num);
    }
    result.add(list);
  }

  private void swap(int i, int j, int[] nums){
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

Performance

The time complexity is 0(n×n!), since there are n! permutations, and we spend 0(n) time to store each one. Having studied this example, we can observe that backtracking only visits each state once, which is why its time complexity should be similar to the graph traversal of O(|V|+|E|).

Conclusion

Summing up the above, backtracking is definitely a perfect algorithmic technique for solving both subset and permutation problems. With the help of its depth-first search method, the backtracking algorithm will inevitably find the required solution in strict compliance with all given constraints.

Since 1950, when the term “backtracking” was coined by D. H. Lehmer, an American mathematician, backtracking managed to handle a wide range of practice problems, starting from printing all paths from a given source to a destination and finishing with finding the shortest safe route in a path with landmines. In this regard, the next time you deal with either permutations or subsets, I strongly recommend that you use the backtracking algo pattern.

Backtracking LeetCode Pattern: Permutations vs Subsets in Java

The basics of backtracking

Subsets

Problem description

Idea

Example

Solution

Performance

Permutations

Problem description

Idea

Example

Solution

Performance

Conclusion

List of references