Java.Algo.Backtracking.AllPermutations

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfsBacktrackingAllPermutations(nums, 0, res);
        return res;
    }

    private static void dfsBacktrackingAllPermutations(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i); // choose
            dfsBacktrackingAllPermutations(nums, start + 1, result); // explore
            swap(nums, start, i); // un-choose (backtrack)
        }
    }

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

🧠 Example: Input [1, 2, 3]

Let’s trace it!

Step 1: start = 0

Loop: i = 0 → 2

i = 0:

• swap(0,0): [1, 2, 3]
• backtrack(start=1)

Step 2: start = 1

Loop: i = 1 → 2

i = 1:

• swap(1,1): [1, 2, 3]
• backtrack(start=2)

Step 3: start = 2

Loop: i = 2

• swap(2,2): [1, 2, 3]
• backtrack(start=3) → base case → add [1,2,3]
• backtrack and swap(2,2)

i = 2:

• swap(1,2): [1, 3, 2]
• backtrack(start=2)

start=2:

• swap(2,2): [1,3,2]
• backtrack(start=3) → base case → add [1,3,2]
• backtrack and swap(2,2)
• backtrack to start=1 and swap(1,2) back → restore [1,2,3]

i = 1:

• swap(0,1): [2,1,3]
• backtrack(start=1)…

→ And so on…