问题描述:
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], ]
原问题链接:https://leetcode.com/problems/combinations/
问题分析
关于这个问题在之前一篇讨论排列组合的文章里有讨论过。求给定数字范围的组合时,它遵循一个如下的关系:
void combine(源数据集合a, 目的数据集合b, 当前迭代起始点begin, 当前目标数据集合位置cur, int n) { if(cur == n) //输出数组b for(集合a中间从begin到end的元素i) { b[cur] = a[i]; combine(a, b, i + 1, cur + 1, n); } }
概括起来说就是每次我们从一个给定的位置上开始往后取元素,取了一个元素之后继续在它后面的位置递归的取下一个元素。这样就形成了集合取元素的组合。在详细的实现里我们用一个list保存当前取了的元素,采用拷贝构造传递上一个调用的参数。详细的实现如下:
public class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); combine(n, k, 1, result, new ArrayList<>()); return result; } public void combine(int n, int k, int start, List<List<Integer>> result, ArrayList<Integer> l) { if(k == 0) { result.add(l); return; } for(int i = start; i <= n; ++i) { ArrayList<Integer> a = new ArrayList<>(l); a.add(i); combine(n, k - 1, i + 1, result, a); } } }
在上述的实现里,通过在递归的函数里不断创建新的数组,但是新建的数组又是基于原有参数的基础创建的。这种传递的手法有点类似于immutable的实现思路。值得仔细推敲。
相关推荐
Combinations of a Phone Number 电话号码的字母组合 回溯法,递归 / Backtrack,Recursion 回溯+递归 Daily Challenge 2020/08/26 20 Valid Parentheses 有效的括号 Stack / 栈 用栈实现配对 Daily Challenge 2020/...
combinations, permutations import random import itertools import collections from fractions import Fraction from collections import Counter import operator import re from functools import reduce from ...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
java lru leetcode Leetcode 问题的解决方案 问题 解决方案 0001_Two_Sum 0002_Add_Two_Numbers 0003_Longest_Substring_Without_Repeating_Characters ...0004_Median_of_Two_...0017_Letter_Combinations_of_a_Phone_N
leetcode 2 sum c leetcode 力扣(Leetcode)编程题,JavaScript版本。 编号 中文题目 英文题目 题目描述 JavaScript 难度 1 Two ...Combinations of a Phone Number DFS 中等 18 4Sum 中等 19 Remo
leetcode 316 Every Day Leetcode This project is created to record the ...leetcode. ...设置一个辅助栈专门用于放置当前最小的值,每次压栈时主栈压入新数据,辅助栈压入当前最小数据 ...Combinations
Combinations (medium) --locked √ 357 Count Numbers with Unique Digits(medium) 547 Friend Circles (medium) 51 N-Queens (hard) 132 Palindrome Partitioning (hard) 212 Word Search II (hard) DFS /二叉树 ...
执行 名称规则#Index#。#Function#.go索引表示leecode中的数字 测试用例 名称规则#Index#。#Function#_test.go 通用定义 ...letterCombinations 0018 四数之和 四和 0019 删除链表的倒数第N个
Combinations of a Phone Number Medium 回溯、暴力 0034 Find First and Last Position of Element in Sorted Array Medium 二分 0039 Combination Sum Medium 回溯 0040 Combination Sum II Medium 回溯 0046 ...
Combinations of a Phone Number 093:Restore IP Addresses 树的遍历问题也可以用这种思想来解释。只不过是特殊的递归而已。(只有两路,不用循环) 题型二:动态规划(要整理搜索和DP的区别,都可以用一个状态转移...
Combinations of a Phone Number backtracking int solution[MAX_DIMENSION]; void Backtracking(int dimension) { if(solution is well-generated) { process solution return; } for( x = each value of current ...
leetcode 2 LeetCode - 30 Days 前言 相信所有写程式的人在面试前,总是在揣测在白板题会被问到什么问题,而我们最常听到的准备方式就是“刷”。上有数百个可能是面试官问你...Combinations and Permutations 目录 ref:
leetcode 刷题笔记 记录一些刷题细节,很惭愧只做了一点微小的工作 4.13 162题. Find Peak Element.Binary search,需要比较nums[mid]和nums[mid+1]. 4.12 212题. Word Search II. 用trie tree存word list,然后dfs. ...
Combinations of a Phone Number: 这题是要找到号码对应字符串的所有组合。用字典来表示数字到字符串的组合。然后遍历数字串。使其对应的字母list与前面已有的组合进行 连接即可。 19.Remove Nth Node From End of ...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持...Combinations of a Phone Number 018 4Sum 020 Valid Parentheses 022 Generate Parentheses 028 Implement strStr() 031 Next Permutat
leetcode 分类LeetCode-Java-接受 这是 Leetcode 问题的 Java 解决方案。 细节 标题和答案格式 /* * 17. Letter Combinations of a Phone Number * Target: Given a string containing digits from 2-9 inclusive, ...
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most ...
leetcode 力码锈 问题 # 标题 命令 1 cargo run --bin 1-two-sum 2 cargo run --bin 2-add-two-numbers 3 cargo run --bin 3-longest-substring-without-repeating-characters 7 cargo run --bin 7-reverse-integer ...
题目来源:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 题目 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 ...
2. combinations获取所有的组合情况,permutations可以获取所有的排列情况 3. 限制时间范围 4. 转化为字符型