Backtracking

2 flashcards · Other · by Steven Bui

1. 17. All Letter Combinations of a Phone Number Given a string with the digits 2-9 (inclusive), so no 0 or 1, return all of the possible letter combinations that a given phone number could be. 2 - abc 3 - def 4 - ghi 5 - jkl 6- mno 7 - pqrs 8 - tuv 9 - wxyz ex. Input: "23" Output: ["ad", "ae", ..., "ce", "cf"] ---------------------------------------------------------------------------------- public List<String> method (String digits) { .... }

   Approach: First, create a private static String[] field, where each index of the array corresponds to the letters that a number can be. Then, you are going to want to take a recursive approach. In the main method, create a new List<String> to be returned. Then, call a helper backtrack method that takes in 4 parameters: the List<String> being returned, a new StringBuilder(), the given phone number, and the current index of the phone number to work off of. Then, in the helper backtrack method, cr…

2. 77. Combinations Given 2 numbers n and k, where k is the size of a single combination and n is the highest integer possible for all combinations (from 1 to n, inclusive), return all possible combinations. Duplicate numbers cannot be in a combination, and numbers in a combination should be in order. ex. Input: n = 4, k = 2 Output: [ [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method…

   Approach: You are going to want to take a recursive approach. In the main method, initialize a List<List<Integer>> to be returned. Then, call a helper backtrack method that takes 5 parameters: the List<List<Integer>> to be returned, a new List<Integer>, the value of n, the value of k, and a number representing what index of a single combination that the backtracking should start at. Then, in the helper backtrack method, create the base case: if the size of the combination is k, you can make a C…