一、問題描述

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], ]

二、問題分析

這道題是典型的backtracking類題目，這類題目感覺起來有點枚舉的感覺（把所有的情況列出來）。這類題有類似的處理方式，可以參看generate parentheses，有回溯的基本解釋。

三、Java AC 代碼

public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> item = new ArrayList<Integer>();if (k > n || n <= 0 || k <= 0) {return res;}dfsHelper(res, item, 1, n, k);return res;}public void dfsHelper(List<List<Integer>> res, List<Integer> item,int start, int n, int k) {if (item.size() == k) {res.add(new ArrayList<Integer>(item));return;}for (int i = start; i <= n; i++) {item.add(i);dfsHelper(res, item, i+1, n, k);item.remove(item.size() - 1);}}

總結

以上是生活随笔為你收集整理的【leetcode】【77】Combinations的全部內容，希望文章能夠幫你解決所遇到的問題。

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