1、描述

给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为target的组合。

candidates 中的数字可以无限制重复被选取。

说明：1）所有数字（包括target）都是正整数。

            2）解集不能包含重复的数组。

例1：输入：candidates = [2, 3, 6, 7], target = 7

          所求解集为：[  [7],  [2, 2, 3]   ]

例2：输入：

          所求解集为：[  [2, 2, 2, 2],  [2, 3, 3],  [3, 5]  ]

 

2、算法

思想：递归回溯算法，数组需先排序

var result = [[Int]]()
func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        /*
         递归回溯：数组先排序
         */
        var arr = [Int]()
        var candi = candidates.sorted()
        findCombinationSum(candi, 0, target, arr)
        return result
    }
private func findCombinationSum(_ candidates: [Int], _ start: Int, _ residue: Int, _ arr: [Int]){
        if residue == 0 {
            result.append(arr)
            return
        }
        //基于原数组是排好序的数组的前提，因为如果计算后面的剩余，只会越来越小
        for i in start..<candidates.count {
            if candidates[i] > residue{
                break
            }
            let array = arr + [candidates[i]]
            //因为元素可以重复使用，这里递归传下去的是i而不是i+1
            //residue-candidates[i]表示下一轮的剩余
            findCombinationSum(candidates, i, residue-candidates[i], array)
        }
    }