Chapter 2 - Implicit Tree and Backtracking

We can also treat lists as a tree!

Permal Algorithm

In CS310 we are familiar with the permal algorithm, in reality, this is just backtracking. Backtracking is the idea that we can diverge lists to a tree, and if something doesn't work out we can end the path of the tree and try the other path of the tree.

Permall:

global Buffer[1..n];
procedure PermDriver(n;;);
    output: Prints all n! permutations of 1 through n;
    for i ← 1 to n do Buffer[i] ← i endfor; { initializes Buffer[1..n] }
    Permall(n)
end_PermDriver;

global n; { just to keep the parameter list less cluttered }
procedure Permall(h;;); { h = tree_height of current vertex }
    local i; { remember which child to process next in each iteration }
    if h equals zero then print Buffer[1..n] endif;
    for i ← 1 to h do { simulates: foreach child i of the current vertex at this height do }
        swap Buffer values in location h and location i;
        Permall(h - 1); { recurse }
        swap Buffer values in location h and location i
    endfor { <- this swap is proven to restore Buffer perfectly by induction starting with height 1. }
end_Permall;

Applications of Permall (Backtracking)

How do I get all the permutation of a list?

We can literally copy and modify from the permal!

def perm(arr):
    res = []
    def helper(current_arr):
        if len(current_arr) == len(arr):
            res.append(current_arr.copy())
            return
        for n in arr:
            if n in current_arr:
                continue
            current_arr.append(n)
            helper(current_arr)
            current_arr.pop()
    helper([])
    return res

Permutation is just a rearrangement of a list, therefore it cannot have duplicate values. Under the for loop, you can think of .append and .pop as the swapping buffer values in permall. If the length of the current array is the same length as the input array, we have found a possible permutation so we can add it to our result.

How do I get the subsets of a list?

We can also use permall and tweak it

def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def helper(start, temp):
            res.append(temp.copy())  # Add the current subset
            print(temp.copy())
            
            # Loop through the remaining elements, starting from 'start'
            for i in range(start, len(nums)):
                # Include nums[i] in the current subset
                temp.append(nums[i])
                
                # Recurse with the next starting index
                helper(i + 1, temp)
                
                # Backtrack by removing the last element
                temp.pop()

        # Start the recursive process from index 0
        helper(0, [])
        return res

This is how we can understand the code. Start off from the for loop, we have to start from the starting index to the length of nums. We can update the starting index by passing into i + 1 so that this is the starting index for the next recursion. Because permall treats everything as a tree, we don't need a base case we just need to add the current path to the result since it will do a DFS.

Coin Problem? Suppose we have a list of coins that we can use and a target we want to add the coins up to, how do I get the least amount of coins?

def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        print(dp)
        if amount == 0:
            return 0 
        dp[0] = 0

        for i in range(1, amount+1):
            for c in coins:
                if i - c >= 0:
                    dp[i] = min(dp[i], 1 + dp[i-c])
        return dp[amount] if dp[amount] != amount + 1 else -1

procedure MC(n, V, A[1..n]; K[1..V]);
input: the target V and n distinct positive integer coin values: A[1..n];
output: K[i] counts the number of different coin collections with values in A[1..n] that sum to i.

1. Initialize K[1..n] to ∞;
2. for t ← 1 to n do
3.     K[A[t]] ← 1  { which is a best-possible solution for A[t] cents }
4.     for i ← 0 to V − A[t] do
5.         K[i + A[t]] = min{K[i] + 1, K[i + A[t]]}  { insert an A[t] coin into each coin collection summing to i }
6.     endfor
7. endfor
end_MC;

Subset Sum

def subset_sum(nums, target):
    # Initialize the DP array
    dp = [float("inf")] * (target + 1)  # Use `inf` to represent unreachable sums
    dp[0] = 0  # Base case: A sum of 0 requires no elements (or "0 value")

    # Iterate through each number in nums
    for num in nums:
        # Update the dp array from target to num
        for j in range(target, num - 1, -1):
            if dp[j - num] != float("inf"):  # Check if the previous sum is achievable
                dp[j] = min(dp[j], dp[j - num] + num)

• 78. Subsets - My Solution

• 90. Subsets II - My Solution

• 46. Permutations - My Solution

• 47. Permutations II - My Solution

• 31. Next Permutation - My Solution

• 77. Combinations - My Solution

• 39. Combination Sum - My Solution

• 40. Combination Sum II - My Solution

• 322. Coin Change - My Solution

• 518. Coin Change II - My Solution