77. Combinations

February 04, 2017

77. Combinations

Description

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

Analysis

实质上此题就是求subsets的变形,只需要控制好子集中的元素个数即可,代码如下:

code

class Solution {
private:
    void backtracking(vector<vector<int>> & res,vector<int> & temp,int * num,int start,int k,int n){
        if(temp.size()==k){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<n;++i){
            temp.push_back(num[i]);
            backtracking(res,temp,num,i+1,k,n);
            temp.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> temp;
        int * array=new int[n];
        for(int i=1;i<=n;++i)
            array[i-1]=i;
        backtracking(res,temp,array,0,k,n);
        delete array;
        return res;
    }
};

此外,讨论区中还提供了另一种思路,但总感觉存在一种刻意针对此题要求进行拼凑的嫌疑,不能称为通解,下面将该种解法加以记录:

class Solution {
public:
	vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> result;
		int i = 0;
		vector<int> p(k, 0);
		while (i >= 0) {
			p[i]++;
			if (p[i] > n) --i;
			else if (i == k - 1) result.push_back(p);
			else {
			    ++i;
			    p[i] = p[i - 1];
			}
		}
		return result;
	}
};

For example, the (4, 2) test case yields:

Incremented element at index 0
[1, 0]
Moved index to the right, and copied the value from the left
[1, 1]
Incremented element at index 1
[1, 2]
Combination found!
Added [1, 2] as an answer!
Incremented element at index 1
[1, 3]
Combination found!
Added [1, 3] as an answer!
Incremented element at index 1
[1, 4]
Combination found!
Added [1, 4] as an answer!
Incremented element at index 1
[1, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[2, 5]
Moved index to the right, and copied the value from the left
[2, 2]
Incremented element at index 1
[2, 3]
Combination found!
Added [2, 3] as an answer!
Incremented element at index 1
[2, 4]
Combination found!
Added [2, 4] as an answer!
Incremented element at index 1
[2, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[3, 5]
Moved index to the right, and copied the value from the left
[3, 3]
Incremented element at index 1
[3, 4]
Combination found!
Added [3, 4] as an answer!
Incremented element at index 1
[3, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[4, 5]
Moved index to the right, and copied the value from the left
[4, 4]
Incremented element at index 1
[4, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[5, 5]
n exceeded at 0, moving index to the left
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017