leetcode76_leetcode72

全栈程序员站长

发布于 2022-11-05 10:42:22

1750

发布于 2022-11-05 10:42:22

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

一、问题描述

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);
		}
	}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/191636.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年9月19日，如有侵权请联系 cloudcommunity@tencent.com 删除

https