Permutations

Topic: 07. Recursion (Backtracking)

Link: LeetCode 46 - Permutations

1. Logical Breakdown

• [x] Core Logic: Backtracking. Pick an unused number, recurse, backtrack.
• [x] Base Case: List size == Array size.

2. Visualization

graph TD Root["Start"] --> Pick1["Pick 1"] Pick1 --> Pick2["Pick 2"] Pick2 --> Back["Backtrack"]

3. Complexity

• Time: O(N * N!)
• Space: O(N)

4. Code

package com.dsa.recursion;
import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public List<List<Integer>> solve(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tempList.contains(nums[i])) continue;
                tempList.add(nums[i]);
                backtrack(result, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}