leetcode 216. Combination Sum III DFS + 按照index递归遍历

痛定思痛。 2022-06-08 10:12 158阅读 0赞

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

\[\[1,2,4\]\]

Example 2:

Input: k = 3, n = 9

Output:

\[\[1,2,6\], \[1,3,5\], \[2,3,4\]\]

一个典型的DFS深度优先遍历，是一个很经典的问题。

建议和这一道题[leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历][leetcode 377. Combination Sum IV _ _ DP_ _ DFS]、[leetcode 40. Combination Sum II DFS深度优先搜索][leetcode 40. Combination Sum II DFS] 、[leetcode 39. Combination Sum DFS深度优先搜索][leetcode 39. Combination Sum DFS]当到一起学习。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    /*
     * 类似全排列的问题
     * */
    public class Solution 
    {
        
        List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> combinationSum3(int k, int n) 
        {
            List<Integer> one=new ArrayList<>();
            if(k<=0 || n<=0)
                return res;
            getAll(1,k,n,0,one);
            return res;
        }
        private void getAll(int level,int k, int n,int sum,List<Integer> one)
        {
            if(k==0 && sum==n)
                res.add(new ArrayList<>(one));
            else if(k==0 || sum>n)
                return;
            else 
            {
                for(int i=level;i<=9;i++)
                {
                    one.add(i);
                    getAll(i+1, k-1, n, sum+i, one);
                    one.remove(one.size()-1);
                }
            }
        }
    }

下面是C++的做法，就是做一个DFS深度优先遍历，注意递归出口条件的判断的先后顺序

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <string>
    #include <set>
    #include <map>
    #include <algorithm>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> combinationSum3(int k, int n) 
        {
            if (k <= 0 || n <= 0)
                return res;
            getAll(1, k, n, 0, vector<int>());
            return res;
        }
    
        void getAll(int level, int k, int n, int sum, vector<int> one)
        {
            if (k == 0 && sum == n)
                res.push_back(one);
            else if (k == 0 || sum > n)
                return;
            else
            {
                for (int i = level; i <= 9; i++)
                {
                    one.push_back(i);
                    getAll(i + 1, k - 1, n, sum + i, one);
                    one.erase(one.end() - 1);
                }
            }
        }
    };

[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 40. Combination Sum II DFS]: http://blog.csdn.net/jackzhang_123/article/details/77803003
[leetcode 39. Combination Sum DFS]: http://blog.csdn.net/jackzhang_123/article/details/77802950