1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

/*
 * @lc app=leetcode id=46 lang=java
 *
 * [46] Permutations
 *
 * https://leetcode.com/problems/permutations/description/
 *
 * algorithms
 * Medium (77.71%)
 * Likes:    18602
 * Dislikes: 313
 * Total Accepted:    2M
 * Total Submissions: 2.5M
 * Testcase Example:  '[1,2,3]'
 *
 * 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]]
 * 
 * 
 * Constraints:
 * 
 * 
 * 1 <= nums.length <= 6
 * -10 <= nums[i] <= 10
 * All the integers of nums are unique.
 * 
 * 
 */

// @lc code=start

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> path = new ArrayList<>();

        backTrack(nums, path);
        return result;
    }

    public void backTrack(int[] nums, List<Integer> path){
        if(nums.length == path.size()){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0 ; i < nums.length; i++){
            if(!path.contains(nums[i])){
                path.add(nums[i]);
                backTrack(nums, path);
                path.removeLast();
            }
        }
    }
}


// class Solution {
//     List<List<Integer>> result = new ArrayList<>();
//     public List<List<Integer>> permute(int[] nums) {
//         List<Integer> path = new ArrayList<>();
//         int len = nums.length;
//         boolean [] used = new boolean[len];
//         backTrack(nums, path, used);
//         return result;
//     }

//     public void backTrack(int[] nums,
//      List<Integer> path,boolean [] used ){
//         if(nums.length == path.size()){
//             result.add(new ArrayList<>(path));
//             return;
//         }

//         for(int i = 0 ; i < nums.length; i++){
//             if(!used[i]){
//                 path.add(nums[i]);
//                 used[i] = true;
//                 backTrack(nums, path, used);
//                 used[i] = false;
//                 path.removeLast();
//             }
//         }
//     }
// }



// class Main {
//     public static void main(String[] args) {
//         // Create a new Solution instance
//         Solution solution = new Solution();
//         // Create a test case
//         int[] nums = {1, 2, 3};
//         // Get the answer
//         boolean answer = solution.permute(nums);
//         // Print the answer
//         System.out.println(answer);
//     }
// }

// @lc code=end