Permutations

这算是回溯里面的另外一类题了，之前大多数的题都是组合类，而这里是排列类型的问题，自己做的是采用的一种对当前位置进行逐个换位的方法，这种方法比九章上面的官方答案效率更高，但是这种换位的做法在其他的回溯类型题里很少见到，通用性不太好，下面是代码

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        tmp, res = [], []
        self.helper(nums, 0, len(nums), tmp, res)
        return res

    def helper(self, nums, start, end, tmp, res):
        if start >= end:
            ref = tmp[:]
            res.append(ref)
            return 

        for i in xrange(start, end):
            nums[start], nums[i] = nums[i], nums[start]
            self.helper(nums, start + 1, end, tmp, res)
            nums[start], nums[i] = nums[i], nums[start]

下面是比较传统的组合型添加数到临时数组中的做法，个人感觉这种做法不会超时的原因是因为这种回溯题数据规模不可能太大，在数组中线性查找数的存在的时间消耗和搜索本身比是微不足道的

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, tmp = [], []
        self.helper(nums, 0, len(nums), tmp, res)
        return res

    def helper(self, nums, start, end, tmp, res):
        if start >= end:
            ref = tmp[:]
            res.append(ref)
            return 

        for i in xrange(end):
            if nums[i] in tmp:
                continue
            tmp.append(nums[i])
            self.helper(nums, start + 1, end, tmp, res)
            tmp.pop()

Java版本

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        for (int num : nums) {
            tmp.add(num);
        }
        helper(tmp, 0, result);
        return result;
    }

    private void helper(List<Integer> nums, int start, List<List<Integer>> result) {
        if (start == nums.size()) {
            result.add(new ArrayList<>(nums));
            return;
        }

        for (int i = start; i < nums.size(); i++) {
            int temp = nums.get(i);
            nums.set(i, nums.get(start));
            nums.set(start, temp);
            helper(nums, start + 1, result);
            nums.set(start, nums.get(i));
            nums.set(i, temp);
        }
    }
}

Permutations II

还是先用交换位置的方式做这道题，刷到现在终于理解了每一层里面的哈希表查重是什么原因，首先我们必须理解，每一个调用函数层代表一种组合方式里面的对应的一个数字位，如果这样对应起来再去看哈希表的作用，就能发现哈希表是用来保证每一个数字位对于同一个数字只许出现一次，通过这样的方式查重就能保证不出现重复组合了，下面是代码

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.helper(nums, 0, len(nums), res)
        return res

    def helper(self, nums, start, end, res):
        if start >= end:
            ref = nums[:]
            res.append(ref)
            return 

        store = {}
        for i in xrange(start, end):
            if nums[i] in store:
                continue
            store[nums[i]] = 1
            nums[i], nums[start] = nums[start], nums[i]
            self.helper(nums, start + 1, end, res)
            nums[i], nums[start] = nums[start], nums[i]

这里有个follow up，同时也是另外一道LC的求derangement题的所有组合的输出

要求就是求出所有数字都不在它最开始位置上的排列方法，这里其实只需要加上一个原数组在回溯的过程中进行比较就行了

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        self.helper(nums, 0, result, nums[:])
        return result

    def helper(self, nums, count, result, original):
        if count == len(nums):
            result.append(nums[:])
            return 

        checker = set()
        for i in xrange(count, len(nums)):
            if nums[i] not in checker and nums[i] != original[count]:
                checker.add(nums[i])
                nums[i], nums[count] = nums[count], nums[i]
                self.helper(nums, count + 1, result, original)
                nums[i], nums[count] = nums[count], nums[i]