46 Permutations

回溯法的基本应用

Python

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(cur, remains):
            if remains == []:
                return [cur]
            else:
                ans = []
                for i in range(len(remains)):
                    new_remains = remains[::]
                    p = new_remains.pop(i)
                    new_cur = cur[::]
                    new_cur.append(p)
                    ans.extend(dfs(new_cur, new_remains))
                return ans
        return dfs([], nums)

Java

class Solution {
    public void backtrack(int n, ArrayList<Integer> nums, List<List<Integer>> output, int first){
        if(first == n)
            output.add(new ArrayList<Integer>(nums));
        for(int i = first; i < n; i ++){
            Collections.swap(nums, first, i);
            backtrack(n, nums, output, first + 1);
            Collections.swap(nums, first, i);
        }

    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> output = new LinkedList();
        ArrayList<Integer> nums_lst = new ArrayList<Integer>();
        for(int num: nums){
            nums_lst.add(num);
        }
        int n = nums.length;
        backtrack(n, nums_lst, output, 0);
        return output;
    }
}