Deal with subset, permutation, combination problems using backtracking algorithm

It’s often asked during a technical interview: write a function to get the subsets/combinations/permutations for a given set. These problems seem difficult to solve in the first place, but have similarities when applying the backtracking algorithm. In this post, I’ll illustrate how to solve these problems using the backtracking algorithm.

Definitions

Assume we are given a set A, and it contains several elements. For example, A = [1, 2, 3].

• Subset: In definition, a set B is a subset of set A if all elements of B are also elements of A. Note that the empty set is a subset of any set. Set A has 8 subsets: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]].
• Combination: is a selection of the original set. The combination is the same with subset. Except that we usually select combinations for a specific purpose. For example, if we wanna get combinations of set A that add up to the number 4, the only combination we find is [1, 3].
• Permutation: In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The biggest difference between subset and permutation is that: subset is a selection of the original set, where permutation is the arrangement of the original set. Set A has 6 permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Backtracking Algorithm

Assume we are at the starting point of a maze, we’re going to find all possible paths to exit it. For each move, we need to decide the direction of whether to go down or go right. If we reach a dead-end, we need to go back to choose another direction that probably works. This process of continuing moving and backing is a classical example of backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

The backtracking algorithm performs well in finding all valid solutions. Next, I’ll explain how to implement it in subset/combination/permutation problems.

Subset Problems

Problem: Given an integer array nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Explain: As we all know, the empty set is a subset of any set. We can start with the empty set, then gradually add an element to it, until we run out all elements. One thing to notice is: every time we add an element, we need to make sure that it doesn't appear before. To avoid it, we need to append the element from nums[i+1:] .

Process:

Let’s take set = [1,2,3] as an example, to see how we find all subsets

• Step 1: find all subsets start with element nums[0], we add nums[0] to the empty set [] to create a new subset [1]. Start from set [1], we still can add elements from the remaining set [2, 3] to create some new subsets. First, add element 2 to the current subset to create a new subset [1, 2], then we can add the remaining element 3 to this subset to create a new subset [1, 2, 3]. Secondly, we go back to the previous subset [1], add element 3 to create another subset [1, 3].
• Step 2: find all subsets start with element nums[1], we add nums[1] to the empty set [] to create a new subset [2]. Since there’s still one element 3 in remain, we can only create a new element with it [2, 3]
• Step 3: find all subsets start with element nums[2], we add nums[1] to the empty set [] to create a new subset [3]. There’s no element left in the original set. We’ve found all possible subsets.

Code:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtrack(nums, [], res)
        return res
    
    def backtrack(self, nums, path, res):
        res.append(path)
        for i in range(len(nums)):
            self.backtrack(nums[i+1:], path+[nums[i]], res)

Permutation Problems

Problem: Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Explain:

Permutations are arrangements of the original set. The key point is to find all possible arrangements and make sure there’s no duplicate. We can iterate the set then find all permutations starting with the current element.

Process:

Step 1: find all permutations starting with element nums[0]. Now the left elements are [2, 3], we pick elements from it and form the permutation with the left one until the set runs out.

Step 2: find all permutations starting with element nums[1]. Now the left elements are [1, 3], we pick elements from it and form the permutation with the left one until the set runs out.

Step 3: find all permutations starting with element nums[2]. Now the left elements are [1, 2], we pick elements from it and form the permutation with the left one until the set runs out.

Code:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtrack(nums, [], res)
        return res 
    
    def backtrack(self, nums, path, res):
        if not nums:
            res.append(path)
            return 
        
        for i in range(len(nums)):
            self.backtrack(nums[:i]+nums[i+1:], path+[nums[i]], res)

Combination Problems

Problem: Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Explain:

Similar to the previous problem, we can start at the first element in the set, and gradually find combinations that sum to the target. There are two conditions we need to consider during the process: 1). if the current sum equals the target, we’ve found one combination, stop finding 2). if the current sum is greater than the target, we stop finding it.

Process:

Let’s take candidates = [2,3,6,7], target = 7 as an example.

• Case 1: find all combinations start with [2]. Combine with each element from [2, 3, 6, 7], only [2, 2] and [2, 3] can have possible solutions due to the other two’s sum being greater than the target. For [2, 2], it has four more combinations [2, 2, 2], [2, 2, 3], [2, 2, 6], [2, 2, 7], and the sum of [2, 2, 3] equals to the target, we’ve found one combination. [2, 2, 2] is possible to create a combination because it’s less than the target. The possible combinations are : [2, 2, 2, 2], [2, 2, 2, 3],[2, 2, 2, 6],[2, 2, 2, 7], and there’s no valid combination due to the sums are all greater than the target.
• Case 2: find all combinations start with [3]. Combine with each element from [6, 7]: [3, 6] and [3, 7], there are no valid combinations.
• Case 3: find all combinations start with [7]. Itself is one valid combination. And there’s no more possible combination.
• Case 4: find all combinations start with [8]. No combinations found in this case.

Result is: [[2, 2, 3], [7]]

Code:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()
        self.backtrack(candidates, [], res, target)
        return res
    def backtrack(self, candidates, path, res, target):
        if target < 0:
            return 
        if target == 0:
            res.append(path)
            return 
        for i in range(len(candidates)):
            self.backtrack(candidates[i:], path+[candidates[i]], res, target - candidates[i])

Reference

Backtracking

Subset

https://en.wikipedia.org/wiki/Permutation