HackerHeap

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

Example:

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

Solution 1:

class Solution {
    List<List<Integer>> returnList = new ArrayList<>();
    int[] used ;
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> temp = new ArrayList<Integer>();
        used = new int[nums.length];
         findPermutations(nums, 0, temp);
        return returnList;
    }
    
    public void findPermutations(int[] nums, int index, List<Integer> temp){
        
        if(index == nums.length){
            returnList.add(new ArrayList(temp));
            return;
        }
        
        for(int i=0;i<nums.length;i++){
            if(used[i]!=1){
                used[i]=1;
                temp.add(nums[i]);
                findPermutations(nums, index+1, temp);
                temp.remove(temp.size()-1);
                used[i] = 0;
            }
        }
        return;
    }
}