Generate All Combinations Sum K in DSA Typescript - Build from Scratch

Generate All Combinations Sum K

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Finding combinations that sum to a target is useful in budgeting, meal planning, and resource allocation where exact totals are needed.

💼 Career

Backtracking and combination generation are common in coding interviews and algorithm design roles.

1

Create the ingredients array

Create an array called ingredients with these exact numbers: 2, 3, 6, 7

DSA Typescript

// Create the ingredients array with numbers 2, 3, 6, 7
// Your code here

Hint

Use square brackets [] to create an array and separate numbers with commas.

2

Set the target sum

Create a variable called target and set it to 7

DSA Typescript

const ingredients = [2, 3, 6, 7];
// Create a variable called target and set it to 7
// Your code here

Hint

Use const to create a variable that does not change.

3

Write the findCombinations function

Write a function called findCombinations that takes ingredients and target as parameters and returns an array of all unique combinations of numbers from ingredients that sum exactly to target. Each number can be used only once per combination.

DSA Typescript

const ingredients = [2, 3, 6, 7];
const target = 7;

// Write the findCombinations function below
// Your code here

Hint

Use a helper function inside findCombinations to explore combinations recursively. Use sorting and skip duplicates to avoid repeated combinations.

4

Print the combinations

Print the result of calling findCombinations(ingredients, target)

DSA Typescript

const ingredients = [2, 3, 6, 7];
const target = 7;

function findCombinations(ingredients: number[], target: number): number[][] {
    const results: number[][] = [];
    ingredients.sort((a, b) => a - b);

    function backtrack(start: number, path: number[], sum: number) {
        if (sum === target) {
            results.push([...path]);
            return;
        }
        if (sum > target) {
            return;
        }
        for (let i = start; i  start && ingredients[i] === ingredients[i - 1]) continue; // skip duplicates
            path.push(ingredients[i]);
            backtrack(i + 1, path, sum + ingredients[i]);
            path.pop();
        }
    }

    backtrack(0, [], 0);
    return results;
}

// Print the combinations
// Your code here

Hint

Use console.log to print the result of findCombinations(ingredients, target).