[LeetCode - Backtracking] Combinations

fizz 发布于2019-08-16 10:26 / 1998人阅读

摘要：本题与类似，都是用回溯法。求中个数的不同组合，很明显我们需要注意的就是每个数字只能出现一次，这点与不同。

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

本题与Combinations Sum类似，都是用回溯法。求1...n中k个数的不同组合，很明显我们需要注意的就是每个数字只能出现一次，这点与Combinations Sum不同。

代码

 public class Solution {
        List> res=new ArrayList>();
        int num=0;
        public List> combine(int n, int k) {
            num=n;
            if(n==0||k==0) return res;
            combineHelper(1,k,new ArrayList());
            return res;
        }
        private void combineHelper(int index,int count,List pre){
            if(count==0){
                res.add(pre);
                return;
            }
            for(int i=index;i<=num;i++){
                List cur=new ArrayList(pre);
                cur.add(i);
                combineHelper(i+1,count-1,cur);
            }
        }
    }

云服务器 GPU云服务器 backtracking Combinations LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69791.html

leetcode22. Generate Parentheses

摘要：当右括号和左括号的剩余量均为时，及为一个最终结果。而则会在直接原来的对象上进行修改，其指针仍然指向原来的对象。因此在递归的过程中使用一定要注意，对对象的修改不要相互干扰。题目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

骞讳护 2019-08-14 18:35 评论0 收藏0
leetcode17 Letter Combinations of a Phone Number

摘要：题目要求也就是说，将数字对应的字母的排列组合的的所有可能结果都枚举出来，顺序不唯一。这种类型的题目一般需要求出上一种情况的前提下才可以得知下一种情况。这一种数据结构通过来实现。相比于上一种思路中，内存占用更小，而且更加灵活。题目要求 Given a digit string, return all possible letter combinations that the numbe...

snowell 2019-08-14 18:09 评论0 收藏0
leetcode39 combination sum

摘要：在这道题中，我结合了递归的思想来。就是将当前的值作为一个潜在的结果值加入一个结果数组将数组作为当前结果传入下一轮递归。题目要求 Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the ca...

luoyibu 2019-08-16 10:33 评论0 收藏0
LeetCode 关于回溯问题的看法

摘要：回溯算法在算法过程中就是类似于枚举算法，尝试在搜索过程中找到问题的解。回溯算法( BackTrack )在算法过程中就是类似于枚举算法，尝试在搜索过程中找到问题的解。使用回溯算法解题的一般步骤使用回溯算法解题的一般步骤：针对所给问题得出一般的解空间用回溯搜索方法搜索解空间使用深度优先去搜索所有解并包含适当的剪枝操作 LeetCode 使用回溯算法的题目主要有 36 题，...

ASCH 2019-08-15 13:43 评论0 收藏0
LeetCode[22] Generate Parentheses

摘要：复杂度思路注意的地方，要限制左括号和右括号。每出现一次左括号，就相对于限定了，最多只能出现那么多右括号。所以，为了完成这种限定，用来控制。不然会有的情况出现。 LeetCode[22] Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of ...

Jonathan Shieber 2019-08-14 15:02 评论0 收藏0