Title:

Permutations

Specification:

Given a collection of distinct integers,
return all possible permutations.

Examples:

Example 1:

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

Example 2:

Initial Code and Signature:

``` public class PermutationFinderV3 { public List<List<Integer>> permute(int[] nums) { } } ```

Algorithm:

1. Receive a copy of the input sequence and a copy of the permutation sequence.
2. Remove the first element from the copy of the input sequence.
3. Add the removed element to a copy of the permutation sequence.
4. If the length of the copy of the permutation sequence is equal to the length of the original input sequence,
add the copy of the permutation sequence to the list of permutations.
5. Repeat the solution (Go to 1-).

Run-Time Analysis:

GitHub Project:

Code:

``` /** * @author Mahsa Sadi * * @since 2020 - 04 - 09 * * License: Creative Commons * * Copyright by Mahsa Sadi * * * */ import java.util.ArrayList; import java.util.List; public class PermutationFinderV3 { /** * Problem: Permutations * * @see: https://leetcode.com/problems/permutations/ * * Description: * * Given a collection of **distinct** integers, return all possible permutations. * * * Solution: * * 1- Receive a copy of the input sequence and a copy of the permutation sequence. * 2- Remove the first element from the copy of the input sequence. * 3- Add the removed element to a copy of a permutation sequence. * 4- If the length of the copy of the permutation sequence is equal to the length of the original input sequence, * add the copy of the permutation sequence to the list of permutations. * 5- Repeat the solution (Go to 1-). * * * * */ List <List<Integer>> permutationsList; public List<List<Integer>> permute(int[] nums) { List <Integer> sequence = new ArrayList <Integer> (); permutationsList = new ArrayList <List<Integer>> (); for (int i = 0; i < nums.length; i++) sequence.add(nums [i]); List<Integer> permutation = new ArrayList <Integer> (); findPermutations (permutation, sequence); return permutationsList; } public void findPermutations (List<Integer> p, List <Integer> s) { for (int i = 0; i < s.size (); i++) { List <Integer> copyOfS = new ArrayList <Integer> (s); List <Integer> copyOfP = new ArrayList <Integer> (p); copyOfP.add (s.get(i)); copyOfS.remove(i); findPermutations (copyOfP, copyOfS); } if (s.isEmpty()) { permutationsList.add(p); } } public void printPermutationsList () { for (int i = 0; i < this.permutationsList.size(); i++) System.out.println(this.permutationsList.get(i)); } } ```