Leetcode -- Day 61

Combination

Question 1

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
It is also a backstracking tagged problem.

 1     public List<List<Integer>> combine(int n, int k) {
 2         List<List<Integer>> rs = new ArrayList<List<Integer>>();
 3         dfs(rs, n, 1, new ArrayList<Integer>(), k);
 4         return rs;
 5     }
 6     private void dfs(List<List<Integer>> rs, int n, int start, List<Integer> path, int k ){
 7         //the terminate condition, return when every process is finished 
 8         if(k==0){
 9             rs.add(new ArrayList<Integer>(path));
10             return;
11         }
12         //start from 1 to n (i.e. 1,2,3, ... ,n)
13         for(int i = start; i<=n; i++){
14             path.add(i);
15             dfs(rs, n, i+1, path, k-1);
16             path.remove(path.size() - 1);
17         }
18 
19     }

Question 2

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

 1 public class Solution {
 2     
 3     private String[] button;
 4     public List<String> letterCombinations(String digits) {
 5         button = new String[10];
 6         button[0] = "";
 7         button[1] = "";
 8         button[2] = "abc";
 9         button[3] = "def";
10         button[4] = "ghi";
11         button[5] = "jkl";
12         button[6] = "mno";
13         button[7] = "pqrs";
14         button[8] = "tuv";
15         button[9] = "wxyz";
16         
17         List<String> result = new ArrayList<String>();
18         if (digits == null || digits.length() < 1){
19             return result;
20         }
21         dfs(digits, 0, "", result);
22         return result;
23     }
24     
25     public void dfs(String digits, int start, String path, List<String> result){
26         if (start >= digits.length()){
27             result.add(path);
28             return;
29         }
30         String content = button[digits.charAt(start)-'0'];
31         for (int i = 0; i < content.length(); i ++){
32             dfs(digits, start + 1, path+content.charAt(i), result);
33         }
34     }
35 }