Problem Statement

Given a string S give all the valid unique Permutations possible. S might have duplicate characters.

Examples:
Input: [1,2,3]
Output: [1,2,3], [2,1,3], [3

Solution

This question has choices and decisions involved, therefore this should be a recursion problem.

1. Base Case: When input string is null, insert the output string to result array

function permutations(input, output="", result=[]) {
	if(!input.length) {
		result.push(output);
	}
}

1. Store current input in a temorary tempInput

2. Loop through the characters of the input string

   For every character,

   • Eliminate that character from the input string
   • Add that caracter to output string
   • Recursively call permutations(input, output, result)
   • Revert back the input to the original state by assigning input = tempInput

3. Return result

function permutations(input, output="", result=[]) {
	if(!input.length) {
		result.push(output);
	}

	for(let i=0; i<input.length; i++) {
		let char = input[i]
		if(!output.includes(char)) {
			let tempInput = input
			input = input.substring(0,i) + input.substring(i+1)
			output = output + char
			permutations(input, output, result)
			input = tempInput
		}
	}
	return result
}

//Usage
permutations("abc")

Previous

Problems with Backtracking

Next

Largest Number in $K^{th}$ Swap