Permutations

Given a collection of distinct numbers, return all possible permutations.
For example,

• [1,2,3] have the following permutations:
  
• [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

题目大意：给定一个没有重复数字的集合，返回其排列

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/5/22
 * 递归解法
 */
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        boolean[] flag = new boolean[nums.length];
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        permuteRecursion(result, nums, tmp, flag);
        return result;
    }

    public void permuteRecursion(List<List<Integer>> result, int[] nums, ArrayList<Integer> tmp, boolean[] flag) {
        int len = nums.length;

        if (tmp.size() == len) {
            result.add((List<Integer>) tmp.clone());
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!flag[i]) {
                flag[i] = true;
                tmp.add(nums[i]);
                permuteRecursion(result, nums, tmp, flag);
                tmp.remove(tmp.size() - 1);
                flag[i] = false;
            }
        }
    }
}

import java.util.*;
/**
 * Created by gzdaijie on 16/5/22
 * 交换递归解法
 */
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        permuteRecursion(nums, result, 0);
        return result;
    }

    private void swap(int[] nums, int a, int b) {
        if (nums[a] != nums[b]) {
            int t = nums[a];
            nums[a] = nums[b];
            nums[b] = t;
        }
    }

    private void permuteRecursion(int[] nums, List<List<Integer>>result, int index) {
        int len = nums.length;
        if (index == len - 1) {
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < len; tmp.add(nums[i++])); /* empty */
            result.add(tmp);
            return;
        }

        for (int i = index; i < len; i++) {
            swap(nums, index, i);
            permuteRecursion(nums, result, index + 1);
            swap(nums, i, index);
        }
    }
}