46. Permutations
题目:
https://leetcode.com/problems/permutations/
难度:
Medium
Tag是backtracking，感觉最初来莫算法，最自不量力的时候接触到过backtracking，CS106B也有讲过backtracking，只记得讲的很好。
谷歌了一下，看一下backtracking的用法：
Generalized Algorithm:
Pick a starting point.
while(Problem is not solved)
For each path from the starting point.
check if selected path is safe, if yes select it
and make recursive call to rest of the problem
If recursive calls returns true, then return true.
else undo the current move and return false.
End For
If none of the move works out, return false, NO SOLUTON.
这个题目一方面可以看成从[]开始加各种调料，但一般&常见的做法是看成原本的来swap.
两种解法都可以找到解答。
backtracking的本质还是递归
to do - backtrack依旧需要更详细的学习
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
self.helper(nums,0,result)
return result
def helper(self,nums,begin,result):
n = len(nums)
if begin == n:
tmp = nums[:]
result.append(tmp)
return
for i in range(begin,n):
nums[begin], nums[i] = nums[i],nums[begin]
self.helper(nums,begin+1,result)
nums[begin],nums[i] = nums[i],nums[begin]
