Permutations

Problem Statement

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

Approach

The problem can be solved using a backtracking approach. The key idea is to explore all possible permutations of the given numbers.

Once we have a valid permutation, we can add it to the result list. After every recursive call, we backtrack to explore other possible permutations.

Here is a high-level overview of the approach:

1. Define a recursive function that takes the all input array, all permutations (result), current permutation as parameters.
2. If the current permutation size is equal to the input array size, add the current permutation to the result.
3. Iterate over the input array:
   1. If the current element is already present in the current permutation, skip it.
   2. Add the current element to the current permutation.
   3. Recursively call the function with the updated current permutation.
   4. Remove the last element from the current permutation to backtrack.

Implementation

Here is a Java implementation of the above approach:

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

    solve(nums, result, currentGroup);
    return result;
}

private void solve(int[] nums, 
                   List<List<Integer>> result,
                   List<Integer> currentGroup){
    if(currentGroup.size() == nums.length){
        result.add(new ArrayList<>(currentGroup));
        return;
    }

    // O(n) operation
    for(int elem : nums){
        // O(n) operation
        if(!currentGroup.contains(elem)){
            currentGroup.add(elem);
            // O(n-1) operation
            solve(nums, result, currentGroup);
            currentGroup.removeLast();
        }
    }
}

Complexity Analysis

The time complexity for this approach is $O(n \times n!)$ where $n$ is the number of elements in the input array. This is because we are exploring all possible permutations i.e. $n!$ of the input array of size $n$.