关于回溯法:组合总和-II

组合总和 II

题目介绍

给定一个候选人编号的汇合 candidates 和一个指标数 target，找出 candidates 中所有能够使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能应用 一次。

留神：解集不能蕴含反复的组合。

示例：

输出: candidates = [10,1,2,7,6,1,5], target = 8,
输入:
[[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例：

输出: candidates = [2,5,2,1,2], target = 5,
输入:
[[1,2,2],
[5]
]

问题剖析

办法一

在这道问题当中咱们依然是从一组数据当中取出数据进行组合，而后失去指定的和，然而与后面的组合总和不同的是，在这个问题当中咱们可能遇到反复的数字而且每个数字只可能应用一次。这就给咱们减少了很大的艰难，因为如果存在雷同的数据的话咱们就又可能产生数据雷同的组合，比方在第二个例子当中咱们产生的后果 [1, 2, 2] 其中的 2 就可能来自 candidates 当中不同地位的 2，能够是第一个，能够是第三个，也能够是最初一个 2。然而在咱们的最终答案当中是不容许存在反复的组合的。当然咱们能够依照失常的形式遍历，而后将失去的复合要求的后果退出到一个哈希表当中，对失去的后果进行去重解决。然而这样咱们的工夫和空间开销都会加大很多。

在这个问题当中为了防止产生反复的汇合，咱们能够首先将这些数据进行排序，而后进行遍历，咱们拿一个数据来进行举例子：[1, 2 1]，当初咱们将这个数据进行排序失去的后果为：[1, 1, 2]，那么遍历的树结构如下：

上图示意 [1, 1, 2] 的遍历树，每一个数据都有选和不选两种状况，依据这种剖析形式能够结构下面的解树，咱们对下面的树进行剖析咱们能够晓得，在下面的树当中有一部分子树是有反复的（反复的子树那么咱们就回产生反复的后果，因而咱们要删除反复的分支，也就是不进行递归求解），如下图所示：

咱们当初来剖析一下下面图中产生重复子树的起因，在一层当中选 1 的到第二层不选 1 的子树和第一层不选 1 而第二层选 1 的树产生了反复，因而咱们能够在第一层不选 1 第二层选 1 的子树当中进行递归。

依据下面的例子咱们能够总结进去，在同一层当中，如果前面的值等于他后面一个值的话，咱们就能够不去生成“抉择”这个分支的子树，因为在他的后面曾经生成了一颗截然不同的子树了。

当初咱们的问题是如何确定和上一个遍历的节点是在同一层下面。咱们能够应用一个 used 数组进行确定，当咱们应用一个数据之后咱们将对应下标的 used 数组的值设置为 true，当递归实现进行回溯的时候在将对应地位的used 值设置为 false，因而当咱们遍历一个数据的时候如果他后面的一个数据的used 值是 false 的话，那么这个节点就和后面的一个节点在同一层下面。

依据下面的剖析咱们能够写出如下的代码：

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());
      vector<bool> used(candidates.size(), false);
      backtrace(candidates, target, 0, 0, used);
      return ans;
    }

    void backtrace(vector<int>& candidates, int target, int curIdx,
                   int curSum, vector<bool>& used) {if (curSum == target) { // 满足条件则保留后果而后返回
        ans.push_back(path);
        return;
      } else if (curSum > target || curIdx >= candidates.size()) {return;}
      if (curIdx == 0) {
        // 抉择分支
        path.push_back(candidates[curIdx]); 
        used[curIdx] = true;
        backtrace(candidates, target, curIdx + 1, curSum + candidates[curIdx], used);
             // 在这里进行回溯
        path.pop_back();
        used[curIdx] = false;
        // 不抉择分支
        backtrace(candidates, target, curIdx + 1, curSum, used);
      }else {if (used[curIdx - 1] == false && candidates[curIdx - 1] ==
              candidates[curIdx]) { // 在这里进行判断是否在同一层，如果在同一层并且值相等的话 那就不须要进行抉择了 只须要走不抉择的分支及即可
         backtrace(candidates, target, curIdx + 1, curSum, used);
       }else{
         // 抉择分支
         path.push_back(candidates[curIdx]);
         used[curIdx] = true;
         backtrace(candidates, target, curIdx + 1, curSum + candidates[curIdx], used);
         // 在这里进行回溯
         path.pop_back();
         used[curIdx] = false;
         // 不抉择分支
         backtrace(candidates, target, curIdx + 1, curSum, used);
       }
      }
    }
};

办法二

在回溯算法当中咱们个别有两种抉择状况，这一点咱们在后面组合问题当中曾经介绍过了，一种办法是用抉择和不抉择去生成解树，这样咱们将生成一颗二叉树的解树，另外一种是多叉树，上面咱们来看一下后者的解树：

同样对下面的解树进行剖析咱们回发现同样的也存在雷同子树的状况，如下图所示，途中绿色的节点就时雷同的节点：

与前一种办法剖析一样，当以后的数据和同一层下面的前一个数据雷同的时候咱们不须要进行求解了，能够间接返回跳过这个分支，因为这个分支曾经在后面被求解过了。具体的剖析过程如下图所示：

因而和第一种办法一样，咱们也须要一个 used 数组去保留数据是否被拜访过，然而在这个办法当中咱们还能够依据遍历时候下标去实现这一点，因而不须要 used 数组了，代码如下所示：

Java 代码

class Solution {private List<List<Integer>> res = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);
        backtrace(candidates, target, 0, 0);
        return res;
    }

    public void backtrace(int[] candidates, int target, int curSum,
                          int curPosition) {if (curSum == target) // 达到条件则保留后果而后返回
            res.add(new ArrayList<>(path));
        for (int i = curPosition;
             i < candidates.length && curSum + candidates[i] <= target;
             i++) {
              // 如果 i > curPosition 阐明 i 对应的节点和 curPosition 对应的节点在同一层
              // 如果 i == curPosition 阐明 i 是某一层某个子树的第一个节点
            if (i > curPosition && candidates[i] == candidates[i - 1])
                continue;
            path.add(candidates[i]);
            curSum += candidates[i];
            backtrace(candidates, target, curSum, i + 1);
              // 进行回溯操作
            path.remove(path.size() - 1);
            curSum -= candidates[i];
        }
    }

}

C++ 代码

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());
      backtrace(candidates, target, 0, 0);
      return ans;
    }

    void backtrace(vector<int>& candidates, int target, int curIdx, int curSum) {if (curSum == target) {ans.push_back(path);
        return;
      } else if (curSum > target || curIdx >= candidates.size()) {return;}
      for(int i = curIdx; i < candidates.size() && curSum + candidates[i] <= target; ++i) {if (i > curIdx && candidates[i] == candidates[i - 1])
          continue;
        path.push_back(candidates[i]);
        backtrace(candidates, target, i + 1, curSum + candidates[i]);
        path.pop_back();}
    }
};

总结

在本篇文章当中次要给大家介绍了组合问题 II，这个问题如果认真进行剖析的话会发现外面还是有很多很有意思的细节的，可能须要大家认真进行思考才可能领悟其中的精妙之处，尤其是两种办法如何解决反复数据后果的状况。

以上就是本篇文章的所有内容了，我是LeHung，咱们下期再见！！！更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。