Leetcode P0040"Combination Sum II" 题解

2020/08/23 Leetcode

博文中会简要介绍Leetcode P0040题目分析及解题思路。

“Combination Sum II”是一道中等难度的题目,是p0039的变形题,考察的是回溯法,也是深度优先搜索,即DFS。

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

基本思路就是当现有的和小于target的时候继续向下搜索,直到现有的和等于target,或者全部的可能的选择都会导致和大于target时,结束当前探索,回溯到上一层。

除此之外,为了保证无重复排列需要对原数组进行排序。一般去重或者保证无重复,排序是一个很好的解决手段。由于这次的数组里会有重复的值,就需要主动去重,即如果当前值和上一个值相同,则跳过。

以下是Java的题解代码实现。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        
        this.dfs(candidates, 0, target, 0, new ArrayList<>());
        
        return this.combinations;
    }
    
    private List<List<Integer>> combinations = new ArrayList<>();
    
    private void dfs(int[] candidates, int index, int target, int occupied, List<Integer> sequence) {
        if (occupied == target) {
            List<Integer> copied = new ArrayList<>(sequence);
            this.combinations.add(copied);
            return;
        }
        
        for (int itr=index; itr<candidates.length; ++itr) {
            if (occupied+candidates[itr] > target 
                || (itr > index && candidates[itr] == candidates[itr-1]))
                continue;
            
            sequence.add(candidates[itr]);
            this.dfs(candidates, itr+1, target, occupied+candidates[itr], sequence);
            sequence.remove(sequence.size()-1);
        }
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
         sort(candidates.begin(), candidates.end());
        
        vector<int> sequence;
        this->dfs(candidates, 0, target, 0, sequence);
        
        return this->combinations;
    }
    
private: 
    vector<vector<int>> combinations;
    
    void dfs(vector<int>& candidates, int index, int target, int occupied, vector<int>& sequence) {
        if (occupied == target) {
            vector<int> copied(sequence);
            combinations.push_back(copied);
            return;
        }
        
        for (int itr=index; itr<candidates.size(); ++itr) {
            if (occupied+candidates[itr] > target 
                || (itr > index && candidates[itr] == candidates[itr-1]))
                continue;
            
            sequence.push_back(candidates[itr]);
            this->dfs(candidates, itr+1, target, occupied+candidates[itr], sequence);
            sequence.pop_back();
        }
    }
    
};

Search

    Table of Contents