c++ combination - CSDN
  • 实现: (nm) 既需要计算组合的总数 (32)=3; 也需要分别获得每一种组合的情形,用于穷举搜索; 1, 2; 1, 3; 2, 3 1. 递归实现 // picked + toPick == m void comb(int n, vector<... if (toPi...

    实现:

    (nm)

    • 既需要计算组合的总数 (32)=3
    • 也需要分别获得每一种组合的情形,用于穷举搜索;
      • 1, 2; 1, 3; 2, 3

    1. 递归实现

    // picked + toPick == m
    void comb(int n, vector<int>& picked, int toPick){
        if (toPick == 0) { printPicked(picked); return; }
        int smallest = picked.empty() ? 0 : picked.back() + 1;
        for (int next = smallest; next < n; ++next){
            picked.push_back(next);
            comb(n, picked, toPick-1);
            picked.pop_back();
                                    // 关键!!!
        }
    }

    对于 (42) 而言,四个之中选 2 个,调用端代码如下,

    vector<int> picked;             // 开始为空;
    comb(4, picked, 2);
                                    // 第一个参数表示 n = 4,第三个参数表示 m=2

    最终的输出结果为:

    0 1
    0 2
    0 3
    1 2
    1 3
    2 3

    也即,

    • 0 先进数组,1 再进数组 ⇒ toPick == 0, 输出 (0, 1)
    • 1 出数组,2 进数组 ⇒ toPick == 0, 输出 (0, 2)
    • 2 出数组,3 进数组 ⇒ toPick == 0, 输出 (0, 3)
    • 3 出数组,0 出数组 ⇒ next ⇒ 1

    转载于:https://www.cnblogs.com/mtcnn/p/9423899.html

    展开全文
  • and a target number (T), find all unique combinations in C where the candidate numbers sums to T.Each number in C may only be used once in the combination.

    题目

    Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

    Each number in C may only be used once in the combination.

    Note:
    All numbers (including target) will be positive integers.
    Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
    The solution set must not contain duplicate combinations.
    For example, given candidate set 10,1,2,7,6,1,5 and target 8,
    A solution set is:
    [1, 7]
    [1, 2, 5]
    [2, 6]
    [1, 1, 6]


    算法

    DFS

    复杂度

    O(n!)


    #include<iostream>
    #include<vector>
    #include <algorithm>
    
    using namespace std;
    
    class Solution{
    private:
        void dfs(vector<vector<int> > &ans,vector<int> &single,vector<int> &candi,int cur,int rest){
            int sz=candi.size();
            if(rest==0){
                //to avoid [[1,1,1],2]
                if(!single.empty() && cur<sz && single[single.size()-1]==candi[cur])
                    return;
                ans.push_back(single);
                return;
            }
            if(sz<=cur || rest<0)
                return;
    
            //choose cyr
            single.push_back(candi[cur]);
            dfs(ans,single,candi,cur+1,rest-candi[cur]);
            single.pop_back();
    
            //donot choose cur
            //donot contain duplicate combinations
    
            if(!single.empty() && single[single.size()-1]==candi[cur])
                return;
            dfs(ans,single,candi,cur+1,rest);
    
        }
    
    public:
        vector<vector<int> > combinationSum2(vector<int> &nums,int target){
            vector<vector<int> > ans;
            vector<int> single;
            sort(nums.begin(),nums.end());
            dfs(ans,single,nums,0,target);
            return ans;
        }
    };
    展开全文
  • 216. Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers....

    216. Combination Sum III

    Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

    Note:

    All numbers will be positive integers.
    The solution set must not contain duplicate combinations.
    Example 1:

    Input: k = 3, n = 7
    Output: [[1,2,4]]

    Example 2:

    Input: k = 3, n = 9
    Output: [[1,2,6], [1,3,5], [2,3,4]]

    Approach

    1. 这道题也是很经典的递归回溯题,给你一个数n,要求你找有k个元素的组合等于n,组内的元素唯一,组合也唯一。因为是递归回溯,所以我们首先要清楚递归边界和递归式,然后还要选择什么返回值,用来参考是否要回溯。我选的返回值是bool,用来判断当选择这个数的时候,后序是否能成功组合,如果不能,就移除这个数,递归边界就是当这个组合元素数量达到k个,此时要判断组合内元素合是否为n。递归式就是循环判断pos~9这个区间,pos是不断加一,因为题目要有要求元素唯一,所以我传一个pos值,不断加一,缩小区间,避免重复。0ms

    Code

    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int>> ans;
            combination(ans, vector<int>(), 1, n, k, 0);
            return ans;
        }
        bool combination(vector<vector<int>> &ans,vector<int> nums,int pos,int n,int k,int sum) {
            if (sum == k) {
                if (n == 0) {
                    ans.push_back(nums);
                    return true;
                }
                else {
                    return false;
                }
            }
            for (int i = pos; i <= 9; i++) {
                if (n - i >= 0) {
                    nums.push_back(i);
                    if (!combination(ans, nums, i + 1, n - i, k, sum + 1)) {
                        nums.pop_back();
                    }
                }
            }
            return false;
        }
    };
    展开全文
  • [leetcode] 040. Combination Sum II (Medium) (C++)

    索引:[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
    Github: https://github.com/illuz/leetcode



    040. Combination Sum II (Medium)

    链接

    题目:https://leetcode.com/problems/combination-sum-ii/
    代码(github):https://github.com/illuz/leetcode

    题意

    跟 039 一样(给出一些正整数集合,以及一个目标数,从集合中选择一些数使得它们的和等于目标数),不过不能选重复的数。

    分析

    同样暴力 DFS,不过要考虑重复会复杂点。
    还要考虑解集里不能有相同的解。

    代码

    /*
    *  Author:      illuz <iilluzen[at]gmail.com>
    *  File:        AC_dfs_n!.cpp
    *  Create Date: 2015-01-01 11:35:04
    *  Descripton:  just as the version I
    */
    
    #include <bits/stdc++.h>
    
    using namespace std;
    const int N = 0;
    
    class Solution {
    private:
        void dfs(vector<vector<int> > &ans, vector<int> &single,
                vector<int> &candi, int cur, int rest) {
            int sz = candi.size();
            if (rest == 0) {
                // to avoid [[1,1,1], 2]
                if (!single.empty() && cur < sz && single[single.size() - 1] == candi[cur])
                    return;
                ans.push_back(single);
                return;
            }
            if (sz <= cur || rest < 0)
                return;
            // choose cur
            single.push_back(candi[cur]);
            dfs(ans, single, candi, cur + 1, rest - candi[cur]);
            single.pop_back();
            // don't choose cur
            // not contain duplicate combinations
            if (!single.empty() && single[single.size() - 1] == candi[cur])
                return;
            dfs(ans, single, candi, cur + 1, rest);
        }
    public:
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {
            vector<vector<int> > ans;
            vector<int> single;
            sort(num.begin(), num.end());
            dfs(ans, single, num, 0, target);
            return ans;
        }
    };
    
    int main() {
        int tar;
        int n;
        Solution s;
        cin >> n >> tar;
        vector<int> v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
        vector<vector<int> > res = s.combinationSum2(v, tar);
        for (auto &i : res) {
            for (auto &j : i)
                cout << j << ' ';
            puts("");
        }
        return 0;
    }


    展开全文
  • Combination Sum题目内容: 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. The same repeated number may be
  • my_combination in c++

    2011-01-10 00:20:00
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 1)use int array to simu
  • 利用C++实现,算法dfs解决该问题。所谓dfs就是深度优先搜索。深度优先搜索(DFS)是搜索手段之一。是从某个状态开始不断转移状态直到无法转移为止,然后退回到前一步状态继续转移其他状态,可以想象为一个沿树爬行的...
  • Permutation_Combination_C++

    2019-06-18 12:17:40
    [root@node ~]# cat permutation_combination.cpp #include <vector> #include <iostream> usingnamespace std; class sequence { public: void show(int); sequence(int, i...
  • 找出所有可能组合,即使用k个数,相加结果为n。假设数值从1到9,在每个组合中,尽可被使用一次。即组成的组合,数据相互不同。
  • 这个题目有几点值得要提的。 第一,i++这个表达式的值时i并不是i
  • 有人说这一题暴力搜索,O(N^3),naive,哥只要O(N^2) 当然也差不了多少啦哈哈,因为N只有5。...LANG: C++ */ #include &lt;iostream&gt; #include &lt;fstream&gt; #include &...
  • 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. The same repeated number may be chosen from C unlimited...
  • 题目大意是:有一个正整数集合C和一个正整数目标T。现从C中选出一些数,使其累加和恰好等于T(C中的每个数都可以取若干次),求所有不同的取数方案,是一道典型的深度优先搜索题。
  • Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combinat
  • 在我们对现实中的某些事物抽象成类时,可能会形成很复杂的类,为了更简洁的进行软件开发,我们经常把其中相对比较独立的部分拿出来定义成一个个简单的类,这些比较简单的类又可以分出更简单的类,最后由这些简单的类...
  • 题目Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.The same repeated number may be chosen ...
  • 题目描述: Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations incandidateswhere the candidate numbers sums totarget. ...
  • Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...Each number in C may only be used once in the combination...
1 2 3 4 5 ... 20
收藏数 9,135
精华内容 3,654
热门标签
关键字:

c++ combination