Session 14: Back Tracking

Original Session

Date: 30 Nov 2024

Topic: Back Tracking

1. Concept: Move to next item, if it does not work, come back and move to another.

2. Concept: Time Complexity 2^n

1. Rate Maze
   1. GFG here
   2. 
      
      

   // Function to find all possible paths
       public ArrayList<String> findPath(ArrayList<ArrayList<Integer>> mat) {
           // code here
           
           ArrayList<String> ans = new ArrayList();
           func(ans, mat, mat.size(), 0, 0, "");
           return ans;
           
       }
       
       void func(ArrayList<String> ans, ArrayList<ArrayList<Integer>> m, int n, int i, int j, String s) {
           
           if ((i==n-1) && (j==n-1)) {
               
               if (m.get(i).get(j)== 1) {
                   
                   ans.add(s);
               }
               return;
           }
           
           if (i<0 || j<0 || i>=n || j>=n || m.get(i).get(j) == 0) {
               
               return;
           }
           
           m.get(i).set(j, 0);
           
           func(ans,m,n,i+1,j,s+"D");
           func(ans,m,n,i,j-1,s+"L");
           func(ans,m,n,i,j+1,s+"R");
           func(ans,m,n,i-1,j,s+"U");
           
           m.get(i).set(j, 1);
       }

2. Permutations
   1. 46. Permutations
      1. leetcode here

      public List<List<Integer>> permute(int[] nums) {
              
              List<List<Integer>> list = new ArrayList();
              List<Integer> temp = new ArrayList();
      
              func(list, temp, nums);
              return list;
          }
      
          void func(List<List<Integer>> list, List<Integer> temp, int[] nums) {
      
                  if (temp.size() == nums.length) {
                      list.add(new ArrayList(temp));
                  }
      
                  for (int i=0; i<nums.length;i++) {
                      
                      if (temp.contains(nums[i])) {
                          continue;
                      }
      
                      temp.add(nums[i]);
                      func(list, temp, nums);
                      temp.remove(temp.size()-1);
                  }
          }

3. 78. Subsets
   1. leetcode here

      // Iterative Approach
      public List<List<Integer>> subsets(int[] nums) {
              List<List<Integer>> ans = new ArrayList<>();
              List<Integer> temp = new ArrayList<>();
              help(ans, temp, nums, 0);
              return ans;
          } 
          
          private void help(List<List<Integer>> ans, List<Integer> temp, int[] nums, int start) {
              
              ans.add(new ArrayList<>(temp)); // Add a copy of temp
      
              for (int i=start; i<nums.length; i++) {
      
                  if (temp.contains(nums[i])) {
                          continue;
                  }
                  temp.add(nums[i]);
                  help(ans, temp, nums, i+1);
                  temp.remove(temp.size() - 1);
              }
          }|

4. 90. Subsets II
   1. leetcode here

      public List<List<Integer>> subsetsWithDup(int[] nums) {
      
              List<List<Integer>> ans = new ArrayList<>();
              List<Integer> temp = new ArrayList<>();
              Arrays.sort(nums);
              help(ans, temp, nums, 0);
              return ans;   
          } 
          
          private void help(List<List<Integer>> ans, List<Integer> temp, int[] nums, int start) {
              
              ans.add(new ArrayList<>(temp)); // Add a copy of temp
      
              for (int i=start; i<nums.length; i++) {
      
                  if (i>start && (nums[i] == nums[i-1])) {
                      continue;
                  }
                  temp.add(nums[i]);
                  help(ans, temp, nums, i+1);
                  temp.remove(temp.size() - 1);
              }
          }