Possible Duplicate:
Algorithm: Extract subset based on property sum
in the simple case we have an array:
{6, 1, 3, 11, 2, 5,12}
and we want to know all combinations the sum of elements contained in that array to getting 12.
in this case we will get four combinations:
so, how can we do this in BASIC or PHP?. maybe pseudo-code first ;-).
I've been looking but there just got a combination with a predetermined number of elements.
You can try
echo "<pre>";
$sum = 12 ; //SUM
$array = array(6,1,3,11,2,5,12);
$list = array();
# Extract All Unique Conbinations
extractList($array, $list);
#Filter By SUM = $sum
$list = array_filter($list,function($var) use ($sum) { return(array_sum($var) == $sum);});
#Return Output
var_dump($list);
Output
array
0 =>
array
1 => string '1' (length=1)
2 => string '2' (length=1)
3 => string '3' (length=1)
4 => string '6' (length=1)
1 =>
array
1 => string '1' (length=1)
2 => string '5' (length=1)
3 => string '6' (length=1)
2 =>
array
1 => string '1' (length=1)
2 => string '11' (length=2)
3 =>
array
1 => string '12' (length=2)
Functions Used
function extractList($array, &$list, $temp = array()) {
if (count($temp) > 0 && ! in_array($temp, $list))
$list[] = $temp;
for($i = 0; $i < sizeof($array); $i ++) {
$copy = $array;
$elem = array_splice($copy, $i, 1);
if (sizeof($copy) > 0) {
$add = array_merge($temp, array($elem[0]));
sort($add);
extractList($copy, $list, $add);
} else {
$add = array_merge($temp, array($elem[0]));
sort($add);
if (! in_array($temp, $list)) {
$list[] = $add;
}
}
}
}
The problem is NP-Hard. Even determining if there is ANY subset of the problem that sums to the desired number is NP-Hard (known as the subset sum problem), and there is no known polynomial solution to it.
Thus, you should look for an exponantial solution, such as a backtracking one - generate all possible combinations, and check if they are valid.
You can use trimming to get your search faster (for example, if you generate a partial subset of sum 13, no need to check other subsets which are supersets of this subset, since they will definetly won't lead to a solution.
pseudo code:
findValidSubsets(sum,arr,idx,currSolution):
if (sum == 0):
print currSolution
if (sum < 0): //trim the search, it won't be succesful
return
//one possibility: don't take the current candidate
findPermutations(sum,arr,idx+1,currSolution)
//second poassibility: take the current candidate
currSolution.add(arr[idx])
findPermutations(sum-arr[idx],arr,idx+1,currSolution)
//clean up before returning:
currSolution.removeLast()
Complexity is O(2^n) - need to generate at worst case all 2^n possible subsets
Invoke with findValidSubsets(desiredSum,myArray,0,[]), where [] is an empty initial list
if(sum<0) return part.using dynamic programming you can express solution as
solver(sum,start_index)
stop_condition_here_when sum <= 0
r=0
for i=start_index ; i < last_iddex :
r += solver(sum - array[i],i+1)
r += solver(sum ,i+1)
return r
And adding extra memositaion would also speedup this program
You can iterate over the length of the set. In each step, check all subsets of length k:
for k = 1 to size(input):
foreach permutation p of length k:
if sum(p) == 12:
bam!
