Leetcode 216. Combination Sum 3

1. Probelm

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

2. Design

My first idea was using dynamic programming approach. But this problem is not about finding a solution as a value, Rather, it was to find actual path(elements of combination sets).

In this case, we need to care about all the possible cases.

Also Following the constraints of the problem, the range of elements is not wide much. So we can take the ‘Brute force approach’.

Instead of taking a naive brute force, If we can check whether the next step is promising or not, we can reduces the total amount of traversal cases. That is, Backtracking!

My algorithm follows below steps:

• Promising check : If the target number is bigger than the biggest combination sum(1~9), return flase. If current number of elements is bigger than ‘k’, return false.
• Base conidtion If current sum is equal to target, add it into result set and return dfs. If level is equal to 9, just return.

1. Do dfs until you find target sum.
2. If there is no combination during current call stack, backtrack
3. At this time, just do dfs without adding current level.

3. Implementation

class Solution {
    vector<vector<int>> res;
    int maxEl, limit = 45, target;

public:
    bool isPromising(int cur, int size) {
        if(limit < cur || maxEl == size) return false;
        return true;
    }

    void dfs(int level, int sum, vector<int>& comb) {
        if(sum == target && comb.size() == maxEl)
        {
            res.push_back(comb);
            return;
        }

        if(level == 9)
            return;

        if(isPromising(sum, comb.size()))
        {
            int nextLevel = level+1;
            comb.push_back(nextLevel);
            dfs(nextLevel, sum+nextLevel, comb);
            comb.pop_back();
            dfs(nextLevel, sum, comb);
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        maxEl = k; target = n;

        if(limit < n) return res;

        vector<int> temp;
        dfs(0, 0, temp);

        return res;
    }
};

4. Result