46. Permutations

Given a collection ofdistinctnumbers, return all possible permutations.

For example,
[1,2,3]have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution:

Following the logic from image below,

We use DFS, recursion approach.

The tricky part is during dfsVisit for loop iteration. We visit from index 0 to n-1 every time, and only go to another dfsVisit recursion when index i is not in the usedIndex stack.

Parameters to pass, "usedIndex" stack, "cur" current processing permutation, "nums", "res" list for storing results

Note:

Two erroneous submission because:

1. typo. Inconsistent naming. Solution: double check parameter and naming before submit every time
2. parameter undeclared when using it in recursion. Solution: double check parameter and naming before submit every time

class Solution(object):
    # two error submission because: typo (inconsistent naming), no final check on parameter initiation
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        res = []
        usedIndex = []
        self.dfsVisit(usedIndex, nums, res, [])

        return res

    # 1. 定义：dfs to reduce the problem size to last index iteration, store when len = len(nums)
    def dfsVisit(self, usedIndex, nums, res, cur):

        if len(cur) == len(nums):
            res.append( cur[:]) # 3. 出口

        for i in range(len(nums)):
            if i not in usedIndex:
                # 2. 化小：reduce it to a smaller problem
                self.dfsVisit(usedIndex + [i], nums, res, cur + [nums[i]])