Question

Formatted question description: https://leetcode.ca/all/216.html

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.

Example 2:

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

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

2 <= k <= 9
1 <= n <= 60

Algorithm

Regular DFS.

n is the sum of k numbers.

If n is less than 0, return directly.
If n is exactly equal to 0, and the number of digits in out at this time is exactly k, it means that it is a correct solution at this time.

Code

import java.util.ArrayList;
import java.util.List;


public class Combination_Sum_III {
    class Solution {

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            List<Integer> curr = new ArrayList<Integer>();

            dfs(curr, k, 1, n);

            return result;
        }

        private void dfs(List<Integer> curr, int k, int start, int sum) {
            if (sum < 0) {
                return;
            }

            if (sum == 0 && curr.size() == k) {
                result.add(new ArrayList<Integer>(curr));
                return;
            }

            for (int i = start; i <= 9; i++) {
                curr.add(i);
                dfs(curr, k, i + 1, sum - i);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

############

class Solution {
    private List<List<Integer>> ans;

    public List<List<Integer>> combinationSum3(int k, int n) {
        ans = new ArrayList<>();
        dfs(0, n, k, new ArrayList<>());
        return ans;
    }

    private void dfs(int i, int n, int k, List<Integer> t) {
        if (i > 9 || n < 0 || t.size() > k) {
            return;
        }
        if (n == 0 && t.size() == k) {
            ans.add(new ArrayList<>(t));
            return;
        }
        ++i;
        t.add(i);
        dfs(i, n - i, k, t);
        t.remove(t.size() - 1);
        dfs(i, n, k, t);
    }
}

// OJ: https://leetcode.com/problems/combination-sum-iii/
// Time: O(2^9 * 9)
// Space: O(9)
class Solution {
    vector<vector<int>> ans;
    vector<int> tmp;
    void dfs(int k, int n, int start) {
        if (!k || !n) {
            if (!k && !n) ans.push_back(tmp);
            return;
        }
        for (int i = start; i <= min(9, n); ++i) {
            tmp.push_back(i);
            dfs(k - 1, n - i, i + 1);
            tmp.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return ans;
    }
};

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(start, s, t): # s: sum, t: list
            if s > n or len(t) > k:
                return
            if s == n and len(t) == k:
                ans.append(t.copy())
                return

            for i in range(start, 10):
                t.append(i)
                dfs(i + 1, s + i, t)
                t.pop()

        ans = []
        dfs(1, 0, [])
        return ans

############

class Solution(object):
  def combinationSum3(self, k, n):
    """
    :type k: int
    :type n: int
    :rtype: List[List[int]]
    """

    def dfs(k, start, path, subsum, res, visited):
      if len(path) == k and subsum == 0:
        res.append(path + [])
        return
      if len(path) >= k or subsum <= 0:
        return

      for i in range(start, 10):
        if visited[i] == 0:
          visited[i] = 1
          path.append(i)
          dfs(k, i + 1, path, subsum - i, res, visited)
          visited[i] = 0
          path.pop()

    visited = [0] * 10
    res = []
    dfs(k, 1, [], n, res, visited)
    return res

func combinationSum3(k int, n int) [][]int {
	var ans [][]int
	var t []int
	var dfs func(i, n int, t []int)
	dfs = func(i, n int, t []int) {
		if i > 9 || n < 0 || len(t) > k {
			return
		}
		if n == 0 && len(t) == k {
			cp := make([]int, len(t))
			copy(cp, t)
			ans = append(ans, cp)
			return
		}
		i++
		t = append(t, i)
		dfs(i, n-i, t)
		t = t[:len(t)-1]
		dfs(i, n, t)
	}

	dfs(0, n, t)
	return ans
}

using System.Collections.Generic;

public class Solution
{
    public IList<IList<int>> CombinationSum3(int k, int n)
    {
        if (n == 0 || k == 0) return new IList<int>[0];

        var paths = new List<int>[n + 1, k + 1];
        paths[0, 0] = new List<int>();
        for (var c = 1; c <= 9; ++c)
        {
            for (var j = n; j >= c; --j)
            {
                for (var kk = 1; kk <= k; ++kk)
                {
                    if (paths[j - c, kk - 1] != null)
                    {
                        if (paths[j, kk] == null)
                        {
                            paths[j, kk] = new List<int>();
                        }
                        paths[j, kk].Add(c);
                    }
                }
            }
        }

        var results = new List<IList<int>>();
        if (paths[n, k] != null && paths[n, k].Count > 0) GenerateResults(results, new Stack<int>(), paths, k, n, paths[n, k].Count - 1);
        return results;
    }

    private void GenerateResults(IList<IList<int>> results, Stack<int> result, List<int>[,] paths, int k, int n,
        int maxIndex)
    {
        if (n == 0)
        {
            results.Add(new List<int>(result));
            return;
        }
        for (var i = maxIndex; i >= 0; --i)
        {
            var value = paths[n, k][i];
            result.Push(value);
            var nextMaxIndex = paths[n - value, k - 1].BinarySearch(value);
            if (nextMaxIndex >= 0)
            {
                --nextMaxIndex;
            }
            else if (nextMaxIndex < 0)
            {
                nextMaxIndex = ~nextMaxIndex - 1;
            }
            GenerateResults(results, result, paths, k - 1, n - value, nextMaxIndex);
            result.Pop();
        }
    }
}

function combinationSum3(k: number, n: number): number[][] {
    const ans: number[][] = [];
    const t: number[] = [];
    const dfs = (i: number, s: number) => {
        if (s === 0) {
            if (t.length === k) {
                ans.push(t.slice());
            }
            return;
        }
        if (i > 9 || i > s || t.length > k) {
            return;
        }
        t.push(i);
        dfs(i + 1, s - i);
        t.pop();
        dfs(i + 1, s);
    };
    dfs(1, n);
    return ans;
}

216 - Combination Sum III

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions