Given a collection of distinct integers, return all possible permutations.

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

When we see print all, it is backtracking.

Grow the tree

We will use a recursive function growTreeto grow the tree: It’s argument is an array of number that will be used to build the solution, and the partial solutions the the caller has built.

Finding all solution is like growing a tree. For each permutation, it is built from an empty array, the root level.

Then at each level, we will grow the node by appending a number from input to the partial solution each node contains. After appending the number, we recursively call growTree with the new partial solution and a new input that ticks out the number that was just used for partial solution.

We do this for every node in every level.

When we reach leaf node, we must have had a full solution. we append it to a solution array.

class Solution:

    def __init__(self):
        self.sol = []
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        Use DFS
        """
        def recur(path, nums):
            if not nums:
                self.sol.append(path)
                return 

            for i in range(len(nums)):
                recur(path + [nums[i]], nums[:i] +  nums[i + 1:])

        recur([], nums)
        return self.sol

size of solution

The number of permutations is n!. Since we have n choice for the first letter, then n – 1 choice for the second slot and so on. Since What we picked for the first slot is independent of other slots, we multiples all the number of choices.

Why is this technique called backtracking

On Wikipedia, backtracking is defined as “a general algorithm that finds all(or some) solutions to some computational problem, notably Constraint satisfaction problem(CSP), that develops the solution incrementally. The potential solutions will be discarded (AKA, backtrack) as soon as the the algorithm deems it to be invalid.

Can we not passed the array?

Since the numbers are unique, and at the beginning, the input numbers are [0,1… len(nums) – 1]. We could use the length of nums passed into each recursive function as the input.

class Solution:
    def __init__(self):
        self.sol = []
        self.nums = []

    def permute(self, nums: 'List[int]') -> 'List[List[int]]':
        def backtrack(swap_pos = 0):
            if swap_pos == len(self.nums):
                self.sol.append(self.nums[:])
                return


            for i in range(swap_pos, len(self.nums)):
                self.nums[swap_pos], self.nums[i] = self.nums[i], self.nums[swap_pos]
                backtrack(swap_pos + 1)
                self.nums[swap_pos], self.nums[i] = self.nums[i], self.nums[swap_pos]

        self.nums = nums
        backtrack()
        return self.sol

In the code above, we are able to use the input to store each candidate solution. As soon as we find a solution, we backtrack so the input is back to the previous state and other branch can use it to build their candidate solution.

Bugs

When I append to solution, I didn’t use copy [:]. So only the address of self.nums is appended and in the end, the solutions are all the same.