leetcode_077 Combinations

981 단어
제목 분석: 숫자 n과 숫자 k를 주고 1~n에 k개수를 포함하는 모든 가능한 조합수를 구한다.
문제 해결 방법:
차례로 거슬러 올라가 실현하다.
1) 한 번 귀속하여 하나의 숫자를 기입하고 기입한 숫자는 현재의 값보다 작으면 안 되며 중복을 방지한다.
2) 거슬러 올라가 마지막에 입력한 숫자를 꺼내서 윗층으로 거슬러 올라간다.
3) 입력한 숫자의 개수가 k보다 작으면 1을 실행하고 숫자를 계속 기입한다.만약 k개의 숫자에 도달하면 한 번에 기입하고 출력합니다
가능한 결과를 차례로 거슬러 올라가다.
class Solution
{
	public:
		//   
		void combine_helper(int start, int num, int n, int k, vector<int> temp, vector< vector<int> > &result)
		{  
			if (num == k)
			{
				result.push_back(temp);
				return ;
			}
			for (int i = start; i < n; i++)
			{
				temp.push_back(i + 1);
				combine_helper(i + 1, num + 1, n, k, temp, result);
				temp.pop_back();
			}
		}
		vector< vector<int> > combine(int n, int k)
		{
			vector< vector<int> > result;
			if (n == 0 || k == 0)
				return result;
			vector<int> temp;
			combine_helper(0, 0, n, k, temp, result);
				return result; 
		}
};

좋은 웹페이지 즐겨찾기