摘要:題目為求從到的自然數里取個數的所有組合全集。使用遞歸的模板,建立函數。模板如下也可以不建立新的,而是遞歸調用之后刪去中最后一個元素
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); } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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...
閱讀 1416·2021-10-08 10:05
閱讀 3060·2021-09-26 10:10
閱讀 883·2019-08-30 15:55
閱讀 504·2019-08-26 11:51
閱讀 441·2019-08-23 18:10
閱讀 3849·2019-08-23 15:39
閱讀 658·2019-08-23 14:50
閱讀 767·2019-08-23 14:46