Permutations

Given a collection of 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].

• Time: O(n)
• Space: O(1)

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] flag = new boolean[nums.length];
    permuteDfs(ret, path, nums, flag);
    return ret;
}

private void permuteDfs(List<List<Integer>> ret, 
            List<Integer> path, int[] nums, boolean[] flag) {
    if (path.size() == nums.length) {
        ret.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!flag[i]) {
            flag[i] = true;
            path.add(nums[i]);
            permuteDfs(ret, path, nums, flag);
            path.remove(path.size() - 1);
            flag[i] = false;
        }
    }
}