首页 > 代码库 > LeetCode_38combinationSum [Combination Sum]

LeetCode_38combinationSum [Combination Sum]

#pragma warning(disable:4996)

#include <cstdio>
#include <tchar.h>
#include <Windows.h>
#include <vector>
using namespace std;

/*
	submit time : 4
		1.Runtime Error
			Last executed input:	[1], 2			// Find it
		2. Wrong Answer
			Input:	[2,3,5], 7
			Output:	[[2,2,3]]
			Expected:	[[2,2,3],[2,5]]
		3. Wrong Answer
			Input:	[1,2], 2
			Output:	[[1,1],[2],[2]]
			Expected:	[[1,1],[2]]
	request :
		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 number of times.

		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 2,3,6,7 and target 7,
		A solution set is:
		[7]
		[2, 2, 3]
*/

//=================QuickSort===================
void Swap(int* data, int i, int j) {
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

int findpivot(int* data, int i, int j) {
	return (i + j) >> 1;
}

int partition(int* data, int l, int r, int pivot) {
	while (l < r) {
		while (data[++l] < pivot);
		while (l<r && data[--r] > pivot);
		Swap(data, l, r);
	}

	return l;
}

void qsort(int* data, int i, int j) {
	if (j <= i) return;

	int pivotIndex = findpivot(data, i, j);
	Swap(data, pivotIndex, j);
	int k = partition(data, i - 1, j, data[j]);
	Swap(data, k, j);
	qsort(data, i, k - 1);
	qsort(data, k + 1, j);
}
//===================END=======================

void helpCombinationSum(vector<vector<int> >& result, vector<int>& solution, int* pStart, int* pLast, int* vernier, int target) {
	if (target == 0) {
		result.push_back(solution);
		return;
	}
	if ((vernier <= pLast && target < *vernier) || (vernier > pLast))
		return;

	int currValue = http://www.mamicode.com/*vernier;>