Day4

77.组合

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

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

示例 1：

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

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

思路：回溯加剪枝

class Solution {
  List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {

        int startIndex = 0;
        backtracking(0, n, k);
        return res;

    }

    void backtracking(int startIndex, int n, int k) {
        if (path.size() == k) {
            ArrayList<Integer> temp = new ArrayList<>(path);
            res.add(temp);
            return;
        }

        for (int i = startIndex; i < n; i++) {
            if (n-i + path.size() < k) {
                continue;
            }
            path.add(i + 1);

            backtracking(i + 1, n, k);
            path.remove(path.size() - 1);
        }
        return;
    }

}

其中

 if (n-i + path.size() < k) {
                continue;
            }

这一段可以替换为

  for (int i = startIndex; i <=n+path.size()-k; i++)

216.组合总和III

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

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

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

示例 1:

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

示例 2:

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

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

思路：回溯加剪枝，其中剪枝操作可以剪两种不同的情况，且用sum记录总和比用path.stream().mapToInt(Integer::intValue).sum()高效

class Solution {
    List<Integer>path = new ArrayList<>();
    List<List<Integer>>res = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        int startIndex = 1;

        backtracking(startIndex,k,n);
        return res;
    }

    private void backtracking(int startIndex,int k ,int n){
        if(path.size()==k){
            if(sum==n){
                res.add(new ArrayList<Integer>(path));
            }
            return;
        }
        for(int i=startIndex;i<=10+path.size()-k;i++){
            if(sum+i>n)return;
            path.add(i);
            sum+=i;
            backtracking(i+1,k,n);
            sum-=path.get(path.size()-1);
            path.remove(path.size()-1);


        }
        return ;
    }
}

17.电话号码的字母组合

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

思路：不同集合的组合问题，不需要startIndex来规定顺序，只需要规定一个index来确定遍历到哪一个string字符串即可，内层字符串遍历每次从0开始即可,也就是一般来讲，回溯算法在处理单层逻辑时只用写一个循环，一般是内层用循环，剩下的起始位置和终点的剪枝操作具体问题具体分析

class Solution {
    StringBuilder path = new StringBuilder("");
    List<String> res = new ArrayList<>();
    int N;

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0)
            return res;
        N = digits.length();
        String[] map = new String[] { " ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        backtracking(digits, map, 0);
        return res;
    }

    private void backtracking(String digits, String[] map, int  OuterstartIndex) {
        if (path.length() == N) {
            res.add(path.toString());
            return;
        }
            String s = map[digits.charAt(OuterstartIndex) - '0'];
            int len = s.length();
            for (int j = 0; j < len; j++) {
                path.append(s.charAt(j));
                backtracking(digits, map, OuterstartIndex + 1);
                path.deleteCharAt(path.length() - 1);
            }
        return;

    }
}