Permutations
A Backtracking Problem

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
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]]
Solution:
 NOTE: I highly recommend going through the Backtracking chapters in the order they are given in the Index page to get the most out of it and be able to build a rocksolid understanding.
 Prerequisite: Backtracking Fundamentals

Suppose we we are computing a permutation perm for
elements in a given array arr[] and if we are forming the permutation
from left to right and if we have already
formed partial permutation perm[0...(i  1)] then
candidates for the position perm[i] would be all the
elements that have not been used in any of the positions in perm[0...(i  1)].
Example: Suppose we need to compute permutations for arr = {1, 2, 3, 4}. Now suppose we are halfway forming a permutation and so far we have gotten partial solution "1, 2 . . ". What would be the third element ? It could be either 3 or 4 because 1 and 2 have already been used and we could use each element only once.
From the above discussion we understand that exhaustive search is a way to go for this problem.
Using our understanding of backtracking and how it works and leveraging our Backtracking Template we get the below working solution.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Don't forget to take indepth look at the other backtracking problems because that is what would make you comfortable with using the backtracking template and master the art of Backtracking:
 Letter Case Permutation
 Power Set
 All Paths Between Two Nodes
 Word Search
 Sudoku
 NQueens
 Word Square
 Generate Parentheses
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn