impl Solution {
    fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new(); // To store all permutations
        let mut current = Vec::new(); // Current permutation
        let mut used = vec![false; nums.len()]; // Track used elements

        // Recursive function to generate permutations
        fn backtrack(
            nums: &[i32],
            current: &mut Vec<i32>,
            used: &mut Vec<bool>,
            result: &mut Vec<Vec<i32>>,
        ) {
            if current.len() == nums.len() {
                result.push(current.clone());
                return;
            }

            for i in 0..nums.len() {
                if used[i] {
                    continue;
                }
                current.push(nums[i]);
                used[i] = true;
                backtrack(nums, current, used, result);
                current.pop(); // Remove the last element to backtrack
                used[i] = false;
            }
        }

        backtrack(&nums, &mut current, &mut used, &mut result);
        result
    }
}