Day22 ＞＞ 77、组合 + 216、组合总和 + 17、电话号码的字母组合

代码随想录-回溯算法

77、组合

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

在递归时通过判断剩余可选元素数量，进行剪枝操作

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

今天状态很差，剩下的题等周末补回来。。。

216、组合总和

17、电话号码的字母组合