LeetCode #46 Permutations

Posted on | Post modified | In , , , , , , , ,

Problem

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

Example

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution

Method: Backtracking

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = []

        def is_a_solution(answer, kth, info):
            return kth == len(info)
        
        def process_solution(answer, kth, info):
            ret.append(answer[:])
        
        def construct_candidates(answer, kth, info):
            return [elem for elem in info if elem not in answer]

        def backtrack(answer, kth, info):
            if is_a_solution(answer, kth, info):
                process_solution(answer, kth, info)
            else:
                kth += 1
                candidates = construct_candidates(answer, kth, info)
                for candidate in candidates:
                    answer.append(candidate)
                    backtrack(answer, kth, info)
                    answer.pop()
        
        backtrack([], 0, nums)
        
        return ret