class SubsetSum {
nums: number[];
target: number;
constructor(nums: number[], target: number) {
this.nums = nums;
this.target = target;
}
greedySolution(): number[] {
let sum = 0;
const result: number[] = [];
// Sort descending for greedy pick
const sorted = [...this.nums].sort((a, b) => b - a);
for (const num of sorted) {
if (sum + num <= this.target) {
result.push(num); // add number if sum not exceeded
sum += num;
}
if (sum === this.target) {
break; // stop if target reached
}
}
return result;
}
backtrackingSolution(): number[] {
const result: number[] = [];
const path: number[] = [];
const backtrack = (index: number, currentSum: number): boolean => {
if (currentSum === this.target) {
result.push(...path); // found valid subset
return true;
}
if (currentSum > this.target || index === this.nums.length) {
return false; // stop if sum exceeded or no more numbers
}
// choose current number
path.push(this.nums[index]);
if (backtrack(index + 1, currentSum + this.nums[index])) {
return true; // found solution
}
path.pop(); // backtrack
// skip current number
if (backtrack(index + 1, currentSum)) {
return true; // found solution skipping current
}
return false; // no solution found here
};
backtrack(0, 0);
return result;
}
}
// Driver code
const nums = [3, 1, 7, 9];
const target = 11;
const subsetSum = new SubsetSum(nums, target);
console.log('Greedy solution:', subsetSum.greedySolution().join(', '));
console.log('Backtracking solution:', subsetSum.backtrackingSolution().join(', '));const sorted = [...this.nums].sort((a, b) => b - a);
sort numbers descending for greedy choice
if (sum + num <= this.target) { result.push(num); sum += num; }
add number if sum does not exceed target
if (currentSum === this.target) { result.push(...path); return true; }
found subset that sums exactly to target
if (currentSum > this.target || index === this.nums.length) { return false; }
stop exploring if sum exceeded or no more numbers
path.push(this.nums[index]); if (backtrack(index + 1, currentSum + this.nums[index])) { return true; } path.pop();
try including current number and recurse
if (backtrack(index + 1, currentSum)) { return true; }
try skipping current number and recurse
Greedy solution: 9, 1
Backtracking solution: 3, 1, 7