Example: Permute - rFronteddu/general_wiki GitHub Wiki

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> out = new LinkedList<>();
        List<Integer> perm = new LinkedList<>();
        // keep track of used index
        boolean[] used = new boolean[nums.length];
        perm (out, perm, nums, used);
        return out;
    }
    
    void perm (List<List<Integer>> out, List<Integer> perm, int[] nums, boolean[] used) {
        if (perm.size() == nums.length) {
            // stop when we reach perm len
            out.add (new ArrayList<>(perm));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                // we are already using this index
                continue;
            }
            perm.add (nums[i]);
            used[i] = true;
            perm (out, perm, nums, used);
            // backtrack
            used[i] = false;
            perm.remove (perm.size() - 1);  
        }
    }
}