46. Permutations

Permutations

Problem Description

Given an array nums of distinct integers, 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]]

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Approach) Iteration

The best way to think about the problem is to imagine each index being moved into each position of the array until all of the combinations have been satisfied at least once.

The following diagram is how I imagined solving the problem. I used the given input of [1, 2, 3] as it was easier to visualize and perform the steps.

The Solution

The following code is what I used to solve the permutation problem. I used both iteration and recursion to solve this particular problem.

const permute = (nums) => {
  let result = []
  const p = (arr, tempArray = []) => {
    if (arr.length === 0) {
      result.push(tempArray);
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        p(curr.slice(), tempArray.concat(next));
      }
    }
  }
  p(nums);
  return result;
}

Approach) Backtracking

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
   const output = [];

	const backtrack = (path, rest) => {
		// valid permutation created: exhausted all elements
		if (rest.length === 0) return output.push([...path]);

		for (let i = 0; i < rest.length; i++) {
			const cv = rest[i];
			const L = rest.slice(0, i); // left subarray
			const R = rest.slice(i + 1); // right subarray
			const newRest = [...L, ...R]; // backtrack with inserted element removed
            path.push(cv);
			backtrack(path, newRest);
			path.pop(); // backtrack
		}
	};

	backtrack([], nums);
	return output;

};

Approach) Breadth-First Search (BFS)

Each queue element will have two arrays:

• The first array is the current sequence we have constructed so far.
• The second array is the remaining numbers from nums.

For every element of the queue, we add a new element for every remaining number. For example:
if our nums = [1,2,3] and we dequeued the following element: [ [1], [2, 3] ], then:
We iterate through the second array and add [ [1,2], [3] ] and [ [1, 3], [2] ] to the queue.

var permute = function(nums) {
    
    const result = [];
    const queue = [];
    
    queue.push([[], nums]);
    
    while(queue.length){
        const [currentSequence, availableNumbers] = queue.shift();
        
        if(availableNumbers.length === 0)
        {
            result.push(currentSequence);
            continue;
        }
            
        
        for(let i =0; i < availableNumbers.length; i++)
        {
            const number = availableNumbers[i];
            queue.push([
                [...currentSequence, number], 
                [...availableNumbers.slice(0, i), ...availableNumbers.slice(i + 1)]
            ]);    
        }   
    }
    
    return result;
};

Approach) Divide and Conquer

var permute = function(nums) {
    if (!nums.length) return nums;
    let output = [];
    let _r = (_nums) => {
        if (_nums.length == 1) return [_nums];
        // divide
        let [head, permutations] = [_nums.slice(0, 1), _r(_nums.slice(1,))];
        // conquer
        let output = [];
        for (let permutation of permutations) {
            for (let i = 0; i < permutation.length + 1; i++) {
                output.push([...permutation.slice(0,i), head, ...permutation.slice(i,)]);
            }
        }
        return output;
    }
    return _r(nums);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 46. Permutations

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!