LeetCode 46. Permutations
撰写于 20171108 修改于 20171108 分类 LeetCode
Question
Given a collection of distinct numbers, 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
Interestingly, this problem is somewhat an easy problem, let me tell you why. For back tracking problems,
one must figure out two important point:
 How to move forward to next state?
 When there is no next state available for the program to move to, how to return back to the previous state?
This is part is the detailed solution to this problem, for example [1, 2, 3, 4], to get its permutations,
we can loop the list and get the current item and append it to the result list, and them loop the sublist without the item appended before. For how to return back to the previous state, when the length of the list is zero, return. Note that, we must remove the item from the result list when all the possibile subpermutations of the sublist have been visited.
Accepted Code


In the code self.back_tracking(result, nums[:index]+nums[index+1:])
, the function is to move forward to its sublist. And result.remove(value)
is to remove the item since all the subpermutations of its sublist have been visited.