leetcode #77 in cpp[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

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

Solution:

It is like permutation(#46 and #47). Thus we still use recurrence to search for combinations.

given a list called member that contains i numbers in current combination:

if i == k, push member into our final result

else

for each num[j] in member, i <= j < n;

1. push num[j] into member.

2. recursively find combination of (num[j+1…..n], k-(i+1) )

For example, given [1,2,3,4] and k = 2,

we start from 1, member is []

push 1 into member. Now member is [1], and we just collect 1 number. We need to collect 1 more. Go to next recurrence.

Our current position is 0, we should loop from position 1 to n-1:

1. position 1 which is 2. put 2 into member and member becomes [1,2]. Now we have 2 numbers. put member into final result.

2. position 2 which is 3. put 3 into member and member becomes [1,3]. Now we have 2 numbers, put member into final result

3. position 3 is 4. put 4 into member and member becomes [1,4]. Put member into final result.

recurrence starting from 1 ends

we start from 2, member is []

push 2 into member. Now member is [2], and we just collect 1 number. We need to collect 1 more. Go to next recurrence.

Our current position is 1, we should loop from position 2 to n-1:

1. position 2 which is 3. put 3 into member and member becomes [2,3]. Now we have 2 numbers. put member into final result.

2. position 3 which is 4. put 4 into member and member becomes [2,4]. Now we have 2 numbers, put member into final result

recurrence starting from 2 ends

we start from 3, member is []

push 3 into member. Now member [3], and we just collect 1 number. We need to collect 1 more. Go to next recurrence

Our current position is 2, we should loop from position 3 to n-1:

1. position 3 which is 4. put 4 into member and member becomes [3,4]. Now we have 2 numbers. put member into final result.

recurrence starting from 3 ends

we start from 4, member is []

push 4 into member. Now member [4], and we just collect 1 number. We need to collect 1 more. Go to next recurrence

Our current position is 3, we should loop from position 4 to n-1, but 4 > 3. Thus we terminate the recurrence from 4. member is not pushed.

Code:

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        
        for(int i = 1; i <=n ; i ++){
            find_combine(i,n, k-1,vector<int>(), res);
        }
        return res;
    }
    void find_combine(int i, int n, int left, vector<int> member, vector<vector<int>> &res){
        member.push_back(i);
        if(left == 0){
            res.push_back(member);
            return;
        }
        else{
            i++;
            while(i<=n){
                find_combine(i, n, left - 1, member, res);
                i++;
            }
        }
    }
};

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。