Permutations

1public List<List<Integer>> permute(int[] nums) {
2    List<List<Integer>> result = new ArrayList<>();
3    backtrack(new ArrayList<>(), new HashSet<>(), nums, result);
4    return result;
5}
6
7private void backtrack(List<Integer> current, Set<Integer> used, int[] nums, List<List<Integer>> result) {
8    // Base case: permutation complete
9    if (current.size() == nums.length) {
10        result.add(new ArrayList<>(current));
11        return;
12    }
13
14    // Try each unused number
15    for (int i = 0; i < nums.length; i++) {
16        if (used.contains(i)) {
17            continue;
18        }
19
20        // Choose nums[i]
21        current.add(nums[i]);
22        used.add(i);
23        backtrack(current, used, nums, result);
24
25        // Backtrack
26        current.remove(current.size() - 1);
27        used.remove(i);
28    }
29}