LeetCode第 46 题：全排列

LeetCode 回溯法专题

---

题目来源：LeetCode 第 46 题

回溯法 是一种在探索尝试的过程中来找出所有解的算法。当确定这个候选解不满足求解条件时，就’回溯’返回，尝试其他路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术就叫回溯法。

代码如下：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(index,p):
            if index == len(nums):
                output.append(p[:])
                return
            for i in range(len(nums)):
                if not used[i]:
                    p.append(nums[i])
                    used[i] = True
                    backtrack(index + 1,p)
                    used[i] = False
                    p.pop()


        output = []
        if not nums:
            return []
        used = [False] * len(nums)
        backtrack(0, [])
        return output