https://leetcode-cn.com/problems/permutations/solution/

解法1

    private List<List<Integer>> ans = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        process(nums, used);
        return ans;
    }
    //nums中无重复数字
    private void process(int[] nums, boolean[] used ) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            process(nums, used);
            used[i] = false;
            path.removeLast();
        }
    }

解法2

• i位置只能跟它自己及它后面的数交换

 // 最优解
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    process(nums, 0, ans);
    return ans;
}
public void process(int[] nums, int index, List<List<Integer>> ans) {
    if (index == nums.length) {
        ArrayList<Integer> cur = new ArrayList<>();
        for (int num : nums) {
            cur.add(num);
        }
        ans.add(cur);
    } else {
        for (int j = index; j < nums.length; j++) {
            swap(nums, index, j);
            process(nums, index + 1, ans);
            swap(nums, index, j);
        }
    }
}
private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}