Permutations

This technique uses backtracking to find Permutations in an input data.

How to Identify

• Data Structure Involves: Array, String
• Question Type: When you need to find the Permutations of a given set.

Example

Permutations problem

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]]

Typescript

function permute(nums: number[]): number[][] {
    const result: number[][] = []
    
    function backtracking(permutation: number[]){
        // base case
        if(permutation.length === nums.length) {
            result.push(permutation.slice())
            return
        }
        
        // Recursive
        for(let i = 0; i < nums.length; i++){
            if(permutation.includes(nums[i])) continue; // element already exists, skip
            permutation.push(nums[i])
            backtracking(permutation)
            permutation.pop()
        }
    }

    backtracking([])
    return result
};

Related Problems

	Problems	Difficulty
1	Permutations	Medium
2	Permutations II	Medium