Concise c++ solution using DFS. Accepted with 0ms.


  • 0
    R
    class Solution {
        public:
            void dfs(int k,int n,int pre)
            {
                if(n==0||k==0) 
                {
                    if(n==0&&k==0)
                        m_result.push_back(m_track);
                    return;
                }
                for(int i=pre+1;i<=9;i++) 
                {
                    if(!m_table[i]) 
                    {
                        m_table[i]=1;
                        m_track.push_back(i);
                        dfs(k-1,n-i,i);
                        m_table[m_track[m_track.size()-1]]=0;
                        m_track.pop_back();
    
                    }
                }
                return;
            }
            vector<vector<int> > combinationSum3(int k, int n) {
                for(int i=0;i<10;i++)
                    m_table[i]=0;
                for(int i=1;i<=9;i++) 
                {
                    m_table[i]=1;
                    m_track.push_back(i);
                    dfs(k-1,n-i,i);
                    m_table[i]=0;
                    m_track.pop_back();
                }
                return m_result;
            }
        private:
            vector<vector<int> > m_result;
            vector<int> m_track;
            int m_table[10];
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.