LeetCode DayBackTracking Bahagian 4

491. Susulan Tidak Berkurang

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);

        }
    }

47. Pilihatur II

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!