Memandangkan nombor tatasusunan integer, kembalikan semua kemungkinan urutan tidak menurun yang berbeza bagi tatasusunan yang diberikan dengan sekurang-kurangnya dua elemen. Anda boleh mengembalikan jawapan dalam sebarang susunan.
Contoh 1:
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6, 7,7],[7,7]]
Contoh 2:
Input: nombor = [4,4,3,2,1]
Output: [[4,4]]
Kekangan:
1 <= nums.length <= 15
-100 <= angka[i] <= 100
Halaman Asal
public List<List<Integer>> findSubsequences(int[] nums) { List<List<Integer>> list = new ArrayList<>(); List<Integer> seq = new LinkedList<>(); Set<Integer> set = new HashSet<>(); backTracking(list, seq, nums, 0, set); return list; } public void backTracking(List<List<Integer>>list, List<Integer> seq, int[] nums, int start, Set<Integer> set){ if(start == nums.length){ return; } for(int i=start; i<nums.length; i++){ // pruming the same elements if(i!=start && set.contains(nums[i])){ continue; } if(seq.size() >= 1 && (nums[i] < seq.get(seq.size()-1))){ continue; } // the first element set.add(nums[i]); seq.add(nums[i]); // evaluate non-decreasing if(seq.size() > 1 && nums[i]>= seq.get(seq.size()-2)){ list.add(new ArrayList<>(seq)); } if(seq.size() == 1 || nums[i]>= seq.get(seq.size()-1)){ backTracking(list,seq, nums, i+1, new HashSet<>()); } // backTracking seq.remove(seq.size()-1); } } </p> <h2> 46. Pilihalih </h2> <p>Memandangkan nombor tatasusunan integer berbeza, kembalikan semua pilih atur yang mungkin. Anda boleh mengembalikan jawapan dalam sebarang susunan.</p> <p>Contoh 1:</p> <p>Input: nums = [1,2,3]<br> Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]<br> Contoh 2:</p> <p>Input: nums = [0,1]<br> Output: [[0,1],[1,0]]<br> Contoh 3:</p> <p>Input: nums = [1]<br> Output: [[1]]</p> <p>Kekangan:</p> <p>1 <= nums.length <= 6<br> -10 <= angka[i] <= 10<br> Semua integer nombor adalah unik.<br> </p> <pre class="brush:php;toolbar:false"> public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>(); List<Integer> permutation = new LinkedList<>(); Integer[] numsI = Arrays.stream(nums).boxed().toArray(Integer[]::new); List<Integer> numList = new ArrayList(Arrays.asList(numsI)); backTracking(list, permutation, numList); return list; } public void backTracking(List<List<Integer>> list, List<Integer> permutation, List<Integer> nums){ if(nums.size()==0){ list.add(new ArrayList<>(permutation)); return; } for(int i=0; i<nums.size(); i++){ permutation.add(nums.get(i)); List<Integer> workNums = new ArrayList<>(nums); workNums.remove(Integer.valueOf(nums.get(i))); backTracking(list, permutation, workNums); permutation.remove(permutation.size()-1); } }
Memandangkan koleksi nombor, nombor, yang mungkin mengandungi pendua, kembalikan semua pilih atur unik yang mungkin dalam sebarang susunan.
Contoh 1:
Input: nums = [1,1,2]
Keluaran:
[[1,1,2],
[1,2,1],
[2,1,1]]
Contoh 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
Kekangan:
1 <= nums.length <= 8
-10 <= angka[i] <= 10
Halaman Asal
List<List<Integer>> list = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { List<Integer> permutation = new LinkedList<>(); int[] flags = new int[nums.length]; backTracking(permutation, nums, flags); return list; } public void backTracking(List<Integer> permutation, int[] nums, int[] flags){ if(permutation.size() == nums.length){ list.add(new ArrayList<>(permutation)); return; } Set<Integer> set = new HashSet<>(); for(int i=0; i<nums.length; i++){ // flag work for recursion, set work for loop if(flags[i] != 0 || set.contains(nums[i])){ continue; } int num = nums[i]; permutation.add(num); set.add(num); flags[i] = 1; backTracking(permutation, nums, flags); //recover to flag; flags[i] = 0; permutation.remove(permutation.size()-1); } }
Atas ialah kandungan terperinci LeetCode DayBackTracking Bahagian 4. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!