题解 | #没有重复项数字的全排列#

思路

index 位置以后的数字都有机会来到 index 位置，递归求出所有可能的情况

CODE

import java.util.*;
public class Solution {
    ArrayList> res = new ArrayList();
    public ArrayList> permute(int[] num) {
        ArrayList list = new ArrayList();
        process(num,  0, num.length, list);
        return res;
    }

    // nums[...index] 表示index之前已经做过选择，nums[index ...]表示index以后的位置可以来到index位置
    private void process(int[] nums, int index, int N, ArrayList list) {
        if (index == N) {
            res.add(new ArrayList(list));
            return;
        }

        for (int i = index; i < N; i++) {
            swap(nums, index, i);        // 表明包含 index 以及 index 以后的数有机会来到 index 位置
            list.add(nums[index]);       // 将当前index位置的元素加入到list中
            process(nums, index + 1, N, list);        // 下一个位置的可能情况
            list.remove(list.size() - 1);    // 恢复现场
            swap(nums, index, i);        // 恢复现场
        }
    }

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