【問題描述】[中等]

【解答思路】

1. 回溯

class Solution {List<List<Integer>> lists = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {List<Integer> list = new ArrayList<>();backTrace(list, n, k, 0);return lists;}private void backTrace(List<Integer>list, int n, int k, int depth){if(depth>k){return ;}if(depth == k){lists.add(new ArrayList<>(list));return;}for(int i = 1;i<=n ; i++){list.add(i);backTrace(list, n, k, depth+1);list.remove(list.size()-1);}} }

2. 回溯優化

分析搜索起點的上界進行剪枝

class Solution {List<List<Integer>> lists = new ArrayList<>();public List<List<Integer>> combine(int n, int k) {List<Integer> list = new ArrayList<>();backTrace(list, n, k, 0);return lists;}private void backTrace(List<Integer>list, int n, int k, int depth){if(depth>k){return ;}if(depth == k){lists.add(new ArrayList<>(list));return;} // 只有這里 i <= n - (k - path.size()) + 1 與參考代碼 1 不同for(int i = 1;i <= n - (k - path.size()) + 1 ; i++){list.add(i);backTrace(list, n, k, depth+1);list.remove(list.size()-1);}} }

【總結】

1. 回溯法解決組合問題。和排列問題不同的是，在組合問題中元素的順序不考慮，只需要從當前位置向后尋找。排列問題每次都需要從頭尋找，需要用visited數組記錄訪問過的元素。

2.相關題目

[Leedcode][JAVA][第46題][全排列][回溯算法]
[Leetcode][第81題][JAVA][N皇后問題][回溯算法]
[Leetcode][第60題][JAVA][第k個排列][回溯][DFS][剪枝]

轉載：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

總結

以上是生活随笔為你收集整理的[Leetcode][第77题][JAVA][组合][回溯]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。