ไฝๆธๅญๅฏ่ฝๆๅจๅ้ขๅบ็พ, ๆไปฅ้่ฆ used ้ๅถไฝฟ็จ้็, ไธ่ฝ้ nature order, i = start ไพ้ๅถ็จ้็
use list.contains => O(n)
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
helper(res, new ArrayList<>(), nums);
return res;
}
// 1. 2. 3
// 2. 3 1. 3
private void helper(List<List<Integer>>res , List<Integer> list, int[] nums) {
if (list.size() == nums.length) {
res.add(new ArrayList<>(list));
}
for (int i = 0; i < nums.length; i++) {
if (list.contains(nums[i])) {
continue;
}
list.add(nums[i]);
helper(res, list, nums);
list.remove(list.size()-1);
}
}
}
list.add(nums[i]);
helper(res, list, nums);
list.remove(list.size()-1);
use used[] , replace list.contains
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
boolean used[] = new boolean[nums.length];
helper(res, new ArrayList<>(), used, nums);
return res;
}
// 1. 2. 3
// 2. 3 1. 3
private void helper(List<List<Integer>>res , List<Integer> list, boolean used[], int[] nums) {
if (list.size() == nums.length) {
res.add(new ArrayList<>(list));
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
list.add(nums[i]);
used[i] = true;
helper(res, list, used, nums);
list.remove(list.size()-1);
used[i] = false;
}
}
}