LeetCode DayBackTracking Partie 4

    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. ​​Permutations
</h2>

<p>Étant donné un tableau nums d'entiers distincts, renvoie toutes les permutations possibles. Vous pouvez renvoyer la réponse dans n'importe quel ordre.</p>

<p>Exemple 1 :</p>

<p>Entrée : nums = [1,2,3]<br>
Sortie : [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]<br>
Exemple 2 :</p>

<p>Entrée : nums = [0,1]<br>
Sortie : [[0,1],[1,0]]<br>
Exemple 3 :</p>

<p>Entrée : nums = [1]<br>
Sortie : [[1]]</p>

<p>Contraintes :</p>

<p>1 <= nums.length <= 6<br>
-10 <= nums[i] <= 10<br>
Tous les nombres entiers sont uniques.<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);

        }
    }

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

        }

    }