LeetCode - 40. Combination Sum II

本文主要是介绍LeetCode - 40. Combination Sum II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

40. Combination Sum II

Problem's Link

----------------------------------------------------------------------------

Mean:

给你一个待选集合s和一个数n，选出所有相加之和为n的组合.（每个元素只能选一次）

analyse:

递归求解.

在递归进入下一层时加判断，相邻两个相等则跳过一次，否则如果当前值对应后面组合有答案，将会算进去两次.

Time complexity: O(N)

view code

 /** 
  * ----------------------------------------------------------------- 
  * Copyright (c) 2016 crazyacking.All rights reserved. 
  * ----------------------------------------------------------------- 
  *       Author: crazyacking 
  *       Date  : 2016-03-05-18.56 
  */ 
 #include <queue> 
 #include <cstdio> 
 #include <set> 
 #include <string> 
 #include <stack> 
 #include <cmath> 
 #include <climits> 
 #include <map> 
 #include <cstdlib> 
 #include <iostream> 
 #include <vector> 
 #include <algorithm> 
 #include <cstring> 
 using namespace std; 
 typedef long long( LL); 
 typedef unsigned long long( ULL); 
 const double eps( 1e-8); 
 
 class Solution 
 { 
 public : 
     vector < vector < int >> combinationSum2( vector < int >& candidates , int target) 
     { 
         sort( candidates . begin (), candidates . end()); 
         vector < vector < int >> res; 
         vector < int > combination; 
         combinationSum( candidates , res , combination , target , 0); 
         return res; 
     } 
 private : 
     void combinationSum( vector < int >& candidates , vector < vector < int >> & res , vector < int >& combination , int target , int begin) 
     { 
         if( ! target) 
         { 
             res . push_back( combination); 
             return; 
         } 
         for( int i = begin; target >= candidates [ i ] && i < candidates . size() ; ++ i) 
         { 
             if( i == begin || candidates [ i ] != candidates [ i - 1 ]) 
             { 
                 combination . push_back( candidates [ i ]); 
                 combinationSum( candidates , res , combination , target - candidates [ i ], i + 1); 
                 combination . pop_back(); 
             } 
         } 
         return; 
     } 
 }; 
 
 
 int main() 
 { 
     freopen( "H: \\ Code_Fantasy \\ in.txt" , "r" , stdin); 
     int n , target; 
     while( cin >>n >> target) 
     { 
         cout <<n << " " << target << endl; 
         vector < int > ve; 
         for( int i = 0; i <n; ++ i) 
         { 
             int tmp; 
             cin >> tmp; 
             ve . push_back( tmp); 
         } 
         Solution solution; 
         vector < vector < int >> ans = solution . combinationSum2( ve , target); 
         for( auto p1: ans) 
         { 
             for( auto p2: p1) 
             { 
                 cout << p2 << " "; 
             } 
             cout << endl; 
         } 
     } 
     return 0; 
 } 
 /* 
 
 */ 