algoadvance

Leetcode 46. Permutations

Problem Statement:

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Clarifying Questions:

1. Are all elements in nums distinct?
   • Yes, as per the problem statement.
2. Is there any specific order in which permutations need to be returned?
   • No, the permutations can be returned in any order.
3. What is the maximum length of nums?
   • This isn’t specified, but typically leetcode problems handle input sizes that are manageable within a few seconds of runtime.

Strategy:

To generate all permutations of a list of distinct integers, we can use a backtracking approach. This approach involves constructing permutations in a depth-first manner.

1. Backtracking Algorithm:
   • Use a helper method that will take the current list and the remaining list of nums.
   • For each element in the remaining list, add it to the current list and recursively generate permutations for the rest of the elements.
   • When the remaining list is empty, add the current list to the result.

Code:

import java.util.ArrayList;
import java.util.List;

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

    private void backtrack(int[] nums, List<Integer> current, List<List<Integer>> result) {
        // Base case: If the current list has the same size as nums, a permutation is complete
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        // Recursive case: Try adding each number to the current list
        for (int num : nums) {
            if (!current.contains(num)) { // Ensure we don't add the same number
                current.add(num);
                backtrack(nums, current, result);
                current.remove(current.size() - 1); // Backtrack to try the next possibility
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = solution.permute(nums);
        for (List<Integer> permutation : permutations) {
            System.out.println(permutation);
        }
    }
}

Time Complexity:

The time and space complexity for generating permutations of a list of size n are as follows:

• Time Complexity: O(n * n!)
  • There are n! permutations, and each permutation takes O(n) time to generate.
• Space Complexity: O(n)
  • The space required to store the current permutation and the additional space used by the recursion stack is O(n). The total space for storing all permutations is also significant but usually considered secondary to the main algorithm’s complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?