• 全排列

全排列

手写解法 1[2,3] 2[1,3] 3[1,2]

第一位分别为1,2,3，其余各位分别填入剩余数字

因此可设一个first指针，表示这一轮填入的位置，填入的数字为first ~ n-1

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {
    if (nums.length == 0) {
        return ans;
    }
    ArrayList<Integer> arr = new ArrayList<>();
    for (int num : nums) arr.add(num);

    dfs(arr, 0, nums.length);
    return ans;
}

private void dfs(ArrayList<Integer> arr, int first, int n) {
    if (first == n) {
        ans.add(new ArrayList<>(arr));
        return;
    }

    for (int i = first; i < n; i++) {
        Collections.swap(arr, first, i);
        dfs(arr, first + 1, n);
        Collections.swap(arr, first, i);
    }
}