Session 15: Back Tracking 2

Original Session

Date: 01 Dec 2024

1. 47. Permutations II
   1. leetcode here

   public List<List<Integer>> permuteUnique(int[] nums) {
           
           List<List<Integer>> ans = new ArrayList<>();
           List<Integer> temp = new ArrayList<>();
           boolean[] isUsed = new boolean[nums.length];
           Arrays.sort(nums);
           help(ans, temp, nums, isUsed);
           return ans;
       }
   
       private void help(List<List<Integer>> list, List<Integer> temp, int[] nums, boolean[] isUsed) {
   
           if (temp.size() == nums.length) {
                   list.add(new ArrayList(temp));
                   return;
               }
   
               for (int i=0; i<nums.length;i++) {
   
                   if (isUsed[i] || (i>0 && nums[i]==nums[i-1] && !isUsed[i-1])) {
                       continue;
                   }
   
                   isUsed[i] = true;
                   temp.add(nums[i]);
                   help(list, temp, nums, isUsed);
                   isUsed[i] = false;
                   temp.remove(temp.size()-1);
               }
       }

2. 39. Combination Sum
   1. leetcode here

   public List<List<Integer>> combinationSum(int[] candidates, int target) {
           
           List<List<Integer>> list = new ArrayList();
           Arrays.sort(candidates);
           func(list, new ArrayList<Integer>(), candidates, target, 0);
           return list;
       }
   
       void func(List<List<Integer>> list, List<Integer> temp, int[] candidates, int remaining, int start) {
   
           if (remaining < 0) {
               return;
           }
   
           if (remaining == 0) {
               list.add(new ArrayList(temp));
           }
   
           for (int i=start; i<candidates.length; i++) {
   
               temp.add(candidates[i]);
               func(list, temp, candidates, remaining - candidates[i], i);
               temp.remove(temp.size() - 1);
           }
       }

3. 40. Combination Sum II
   1. leetcode here

   public List<List<Integer>> combinationSum2(int[] candidates, int target) {
           
           List<List<Integer>> list = new ArrayList();
           Arrays.sort(candidates);
           func(list, new ArrayList<Integer>(), candidates, target, 0);
           return list;
       }
   
       void func(List<List<Integer>> list, List<Integer> temp, int[] candidates, int remaining, int start) {
           
           if (remaining < 0) {
               return;
           }
   
           if (remaining == 0) {
               list.add(new ArrayList(temp));
           }
   
           for (int i=start; i<candidates.length; i++) {
   
               if (i>start && candidates[i] == candidates[i-1]) {
                   continue;
               }
               temp.add(candidates[i]);
               func(list, temp, candidates, remaining - candidates[i], i+1);
               temp.remove(temp.size() - 1);
           }
       }

4. 131. Palindrome Partitioning
   1. leetcode here