permuations

import java.util.*;

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        // Start the backtracking process
        generatePermutations(nums, temp, result);

        return result;
    }

    private void generatePermutations(int[] nums, List<Integer> temp, List<List<Integer>> result) {
        // If we've picked as many numbers as in nums, one permutation is complete
        if (temp.size() == nums.length) {
            result.add(new ArrayList<>(temp)); // Add a copy of current permutation
            return;
        }

        // Try every number in nums
        for (int i = 0; i < nums.length; i++) {
            // If the number is already in our current permutation, skip it
            if (temp.contains(nums[i])) continue;

            // Choose the current number
            temp.add(nums[i]);

            // Recursively pick the next number
            generatePermutations(nums, temp, result);

            // Backtrack - remove the last number and try another one
            temp.remove(temp.size() - 1);
        }
    }
}