摘要:题目为求从到的自然数里取个数的所有组合全集。使用递归的模板,建立函数。模板如下也可以不建立新的,而是递归调用之后删去中最后一个元素
Problem
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
ExampleFor example,
If n = 4 and k = 2, a solution is:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
题目为求从1到n的自然数里取k个数的所有组合全集。使用递归的模板,建立helper函数。
模板如下:
void helper(range S, target T, start A, tempArray B) { if (B met T or other requirement) { res.add(B); return; } for (int i starts from A in S) { tempArray C = new tempArray (B); C.add(i); helper(S, T-i, i+1, C); } }
也可以不建立新的tempArray C,而是递归调用helper之后删去B中最后一个元素:
void helper(range S, target T, start A, tempArray B) { if (B met T or other requirement) { res.add(B); return; } for (int i starts from A in S) { B.add(i); helper(S, T-i, i+1, C); B.remove(B.size()-1); } }Solution
public class Solution { List> res = new ArrayList
>(); public List
> combine(int n, int k) { helper(n, k, 1, new ArrayList
()); return res; } private void helper(int n, int k, int start, List pre) { if (pre.size() == k) { res.add(pre); return; } for (int i = start; i <= n; i++) { List cur = new ArrayList (pre); cur.add(i); helper(n, k, i+1, cur); } } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65722.html
摘要:和唯一的不同是组合中不能存在重复的元素,因此,在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...
摘要:第一个分割点第二个分割点第三个分割点 Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....
Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...
Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...
摘要:建立两个堆,一个堆就是本身,也就是一个最小堆另一个要写一个,使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里,更大的数放在最小堆,较小的数放在最大堆。同时,确保最大堆的比最小堆大,才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
阅读 1339·2021-10-08 10:05
阅读 3034·2021-09-26 10:10
阅读 861·2019-08-30 15:55
阅读 481·2019-08-26 11:51
阅读 382·2019-08-23 18:10
阅读 3774·2019-08-23 15:39
阅读 624·2019-08-23 14:50
阅读 740·2019-08-23 14:46