39. 组合总和

很扯。。比方说这个测试用例 [100,200,4,12] 400
如果用dfs的话 递归会很恐怖= =。。要想办法剪枝
下次从第i个位置选择的话。就不会选择左边的 不会产生重复的= =。。

func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {

     
        var remain = target
        var tempArray = Array<Int>()
        var ans = [[Int]]()
        let len = candidates.count
        dfs(&ans,candidates.sorted(),0,len,&remain,&tempArray)
        return ans
    
    }
    
    func dfs(_ ans:inout [[Int]],_ candidates:[Int],_ begin:Int,_ len:Int,_ remain:inout Int,_ tempArray:inout [Int]){
        //说明找到了合适的组合
        if remain == 0 {
            ans.append(tempArray)
        }
        
        //每一层可以选择的
        for i in begin..<len {
            let num = candidates[i]
            if remain >= num {
                remain -= num
                tempArray.append(num)
                dfs(&ans,candidates,i,len,&remain,&tempArray)
                remain += tempArray.removeLast()
            }else {
                
                break
            }
        }
            
    }