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

Generate All Combinations Sum K

📖 Scenario: You are helping a chef who wants to create special dishes by combining ingredients. Each ingredient has a unique number representing its flavor strength. The chef wants to find all possible combinations of ingredients that add up exactly to a target flavor strength K.

🎯 Goal: Build a program that finds and prints all unique combinations of numbers from a given list that sum up to K. Each number can be used only once in each combination.

📋 What You'll Learn

Create an array called ingredients with the exact values: 2, 3, 6, 7

Create an integer variable called K and set it to 7

Write a recursive function called findCombinations that finds all unique combinations of ingredients that sum to K

Print each combination on a separate line with numbers separated by spaces

💡 Why This Matters

🌍 Real World

Finding combinations of items that meet a specific total is useful in meal planning, budgeting, and resource allocation.

💼 Career

This problem teaches recursion and backtracking, which are important for algorithm design and problem solving in software development.

1

Create the ingredients array

Create an integer array called ingredients with the exact values 2, 3, 6, 7 and an integer n that stores the number of elements in ingredients.

DSA C

# Create the ingredients array and its size
// Your code here

Hint

Use int ingredients[] = {2, 3, 6, 7}; and int n = 4; to store the array and its size.

2

Set the target sum K

Create an integer variable called K and set it to 7.

DSA C

#include 

int ingredients[] = {2, 3, 6, 7};
int n = 4;

// Set the target sum K
// Your code here

Hint

Use int K = 7; to set the target sum.

3

Write the recursive function to find combinations

Write a recursive function called findCombinations with parameters int start, int target, int combination[], and int combSize. This function should find all unique combinations of ingredients starting from index start that sum to target. Use a for loop with int i = start; i < n; i++ to explore choices. When target == 0, print the current combination. Avoid using the same element twice in the same position by skipping duplicates.

DSA C

#include 

int ingredients[] = {2, 3, 6, 7};
int n = 4;
int K = 7;

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

Hint

Use recursion with a for loop starting at start. When target == 0, print the combination.

4

Call the function and print all combinations

In the main function, create an integer array called combination with size n. Call findCombinations with arguments 0, K, combination, and 0. Return 0 from main. This will print all combinations that sum to K.

DSA C

#include 

int ingredients[] = {2, 3, 6, 7};
int n = 4;
int K = 7;

void printCombination(int combination[], int combSize) {
    for (int i = 0; i  target) {
            continue;
        }
        combination[combSize] = ingredients[i];
        findCombinations(i + 1, target - ingredients[i], combination, combSize + 1);
    }
}

int main() {
    // Your code here
}

Hint

In main, create int combination[4]; and call findCombinations(0, K, combination, 0);.