[数据结构与算法]39. 组合总和（ 回溯+去重 ）

LeetCode：39. 组合总和

通过下标控制回溯的位置.

不难想到使用回溯法来解决这类问题，关键在于如何去重
[2,3,6,7] 7
从整个解空间来看，第一个节点dfs的搜索结果会出现在第二节点dfs的搜索结果中，从第一个结点开始dfs会遍历出[2,3,2]的结果，第二个节点遍历会遍历出[3,2,2]的结果来
如何避免这种情况 则只要在由3开始遍历的时候不去深度遍历包含2的那一条分支 所以只要在循环中跳过第一个节点2就可以避免[3,2,2]这个重复的解 所以可以指定回溯之后的开始遍历节点来去重 ； 也就是说在同一层的节点不去遍历该节点下的子树中包含之前节点的路径 如：已经遍历过2和2之后的节点了 则在遍历3和3之后的节点时就不需要再遍历3之后包含2的子树了

引: https://leetcode-cn.com/problems/combination-sum/solution/hui-su-by-la-la-la-6r-2/

AC Code

public class Solution {
    IList<IList<int>> ans = new List<IList<int>>();
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        recu(candidates, 0, target, 0, new List<int>());
        return ans;
    }


    public void recu(int[] arr, int index, int target, int k, List<int> list)
    {
        if (k > target) return;

        // 相等的话
        if (k == target)
        {

            ans.Add(new List<int>(list));

            return;
        }

        for(int i = index; i < arr.Length; i++)
        {
            list.Add(arr[i]);
            //遍历数组
            recu(arr, i, target, k + arr[i], list);
            //回溯 
            list.Remove(arr[i]);
        }
    }
}