Implement Backtracking SearchStep 2 of 5

Permutations

12345

Step 2 - permutations

Implement permutations(nums), returning every permutation.

Fix positions left to right. At each position try the unused elements in their original index order, marking one used, recursing, then unmarking. Record a copy when the path is full.

For [1, 2, 3] the order is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

Hints
Starter code
def subsets(nums):
    res = []
    path = []
    def bt(start):
        res.append(list(path))
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res


def permutations(nums):
    """Return every permutation of nums, fixing positions left to right.

    Walk positions front to back; at each position try unused elements in
    their original index order.
    """
    # TODO: track a used[] flag list, append when placing, pop and unmark
    #       when backtracking; record a copy once path is full.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step