46. Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input:
 [1,2,3]

Output:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution

(1) Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        helper(nums, rst, 0);
        return rst;
    }

    private void helper(int[] nums, List<List<Integer>> rst, int start) {
        if (start == nums.length) {
            List<Integer> list = new ArrayList<>();
            for(int num : nums) {
                list.add(num);
            }
            rst.add(list);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, i, start);

            helper(nums, rst, start+1);
            swap(nums, i, start);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

(2) Python

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        rst = []
        rst.append([])
        for num in nums:
            size = len(rst)
            for i in range(size):
                l = rst.pop(0)
                if not l:
                    l.append(num)
                    rst.append(l)
                else:
                    for j in range(len(l)+1):
                        ll = list(l)
                        ll.insert(j, num)
                        rst.append(ll)
        return rst

(3) Scala