77. 组合

力扣题目链接

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

解决思路

1. 创造集合，path用来存放符合条件结果，res存放符合条件结果的集合
2. 终止条件，当path的长度已经到达k，结果收集完毕
3. n - (k - path.size()) + 1，为了减少不必要的分支。k - path.size()是收集结果还需要的元素个数。如果n=4，k=3，path为0，那么startIndex是从1到2可以选择的。

Java实现

class Solution_LC77 {List> res = new ArrayList<>();LinkedList path = new LinkedList<>();public List> combine(int n, int k) {backTrack(n, k, 1);return res;}private void backTrack(int n, int k, int startIndex) {if (path.size() == k) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {path.add(i);backTrack(n, k, i + 1);path.removeLast();}}
}

216.组合总和III

力扣题目链接

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

解决思路

1. 回溯方法的参数，startIndex用来指定遍历的起始位，sum用来指定当前已经累计的和，path用来存放待定的结果集
2. 剪枝，判断累计和大于指定的和，path的长度已经大于k

Java实现

class Solution_LC216 {private List> res = new ArrayList<>();private LinkedList path = new LinkedList();public List> combinationSum3(int k, int n) {backtrack(k, n, 0, 1);return res;}private void backtrack(int k, int targetSum, int sum, int startIndex) {if (sum > targetSum) return;if (path.size() > k) return;if (targetSum == sum && path.size() == k) {res.add(new ArrayList<>(path));}for (int i = startIndex; i <= 9; i++) {sum += i;path.add(i);backtrack(k, targetSum, sum, i + 1);sum -= i;path.removeLast();}}public static void main(String[] args) {List> lists = new Solution_LC216().combinationSum3(3, 7);System.out.println(lists);}}

17.电话号码的字母组合

力扣题目链接

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解决思路

1. 使用字符串的集合用作对于电话号码的映射
2. 循环是根据startIndex获取字符串，字符串是挨个遍历。在进行下一轮回溯，使用index+1
3. 字符串的处理主要是StringBuilder，删除最后一个字符用的是 temp.deleteCharAt(temp.length() - 1);

Java实现

class Solution_LC17 {List res = new ArrayList<>();StringBuilder temp = new StringBuilder();String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return res;}backtrack(digits, 0);return res;}private void backtrack(String digits, int index) {if (temp.length() == digits.length()) {res.add(temp.toString());return;}String str = numString[digits.charAt(index) - '0'];for (int i = 0; i < str.length(); i++) {temp.append(str.charAt(i));backtrack(digits, index + 1);temp.deleteCharAt(temp.length() - 1);}}
}