Permutations medium

Problem Statement

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

Example 1:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1] Output: [[0,1],[1,0]]

Steps and Explanation

This problem requires generating all possible permutations of a given array. We can achieve this using backtracking. Backtracking is an algorithmic technique that explores all possible solutions by incrementally building candidates and abandoning a candidate ("backtracking") as soon as it's determined that the candidate cannot lead to a valid solution.

Here's how the backtracking approach works for this problem:

1. Base Case: If we've added all elements to the current permutation (its length equals the length of the input array), we've found a complete permutation, so add it to the result list.

2. Recursive Step: For each element in the input array that hasn't been used yet:

   • Add the element to the current permutation.
   • Recursively call the function to explore permutations starting with the current permutation.
   • Remove the element from the current permutation (backtracking step). This is crucial to explore other possibilities.

3. Result: The recursive calls explore all possible branches of the permutation tree, and the function returns a list containing all generated permutations.

Code (C#)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> currentPermutation = new List<int>();
        bool[] used = new bool[nums.Length]; // Keep track of used numbers

        Backtrack(nums, used, currentPermutation, result);
        return result;
    }

    private void Backtrack(int[] nums, bool[] used, List<int> currentPermutation, IList<IList<int>> result) {
        if (currentPermutation.Count == nums.Length) {
            result.Add(new List<int>(currentPermutation)); // Add a copy to avoid modification
            return;
        }

        for (int i = 0; i < nums.Length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.Add(nums[i]);
                Backtrack(nums, used, currentPermutation, result);
                currentPermutation.RemoveAt(currentPermutation.Count - 1); // Backtrack
                used[i] = false;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(N!), where N is the length of the input array. This is because there are N! possible permutations.
• Space Complexity: O(N) for the recursion stack and the currentPermutation list. The space used by the result list is also O(N!), but this is usually not considered in the space complexity analysis of backtracking algorithms. The used boolean array takes O(N) space.