46. Permutations.md

46. Permutations

---

Difficulty : Medium

Related Topics : BackTracking

---

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

• mine
  • Java
    • Iterate Runtime: 3 ms, faster than 38.25%, Memory Usage: 39.5 MB, less than 87.41% of Java online submissions

      public List<List<Integer>> permute(int[] nums) {
          List<List<Integer>> res = new LinkedList<>();
          LinkedList<LinkedList<Integer>> list = new LinkedList<>();
          int n = nums.length;
          for(int i = 0; i < n; i++){
              list.add(new LinkedList<>(Arrays.asList(nums[i])));
          }
          while(!list.isEmpty()){
              if (list.getFirst().size() == nums.length){
                  res.addAll(list);
                  break;
              }
              LinkedList<Integer> first = list.removeFirst();
              for(int i = 0; i < n; i++){
                  if(first.contains(nums[i])) continue;
                  LinkedList<Integer> t = new LinkedList<>();
                  t.addAll(first);
                  t.add(nums[i]);
                  list.add(t);
              }
          }
          return res;
      }
      

---

• the most votes

• Backtracking Runtime: 1 ms, faster than 94.06%, Memory Usage: 39.8 MB, less than 66.82% of Java online submissions

  public List<List<Integer>> permute(int[] nums) {
     List<List<Integer>> list = new ArrayList<>();
     // Arrays.sort(nums); // not necessary
     backtrack(list, new ArrayList<>(), nums);
     return list;
  }
  
  private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
     if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
     } else{
        for(int i = 0; i < nums.length; i++){
           if(tempList.contains(nums[i])) continue; // element already exists, skip
           tempList.add(nums[i]);
           backtrack(list, tempList, nums);
           tempList.remove(tempList.size() - 1);
        }
     }
  }
  

---