leetcode 40. Combination Sum II DFS深度优先搜索 + 按照index递归

﹏ヽ暗。殇╰゛Y 2022-06-09 09:46 169阅读 0赞

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

Each number in C 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.  
For example, given candidate set \[10, 1, 2, 7, 6, 1, 5\] and target 8,  
A solution set is:  
\[  
\[1, 7\],  
\[1, 2, 5\],  
\[2, 6\],  
\[1, 1, 6\]  
\]

和上一道题不一样的是这里不允许重复，稍作修改即可。

建议和这一道题[leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历][leetcode 377. Combination Sum IV _ _ DP_ _ DFS]、[leetcode 216. Combination Sum III DFS + 按照index递归遍历][leetcode 216. Combination Sum III DFS _ _index] 、[leetcode 39. Combination Sum DFS深度优先搜索][leetcode 39. Combination Sum DFS]当到一起学习。

**注意处理重复元素的判断**

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Solution {
        
        public List<List<Integer>> combinationSum2(int[] candidates, int target)
        {
            List<List<Integer>> res=new ArrayList<List<Integer>>();
            List<Integer> one=new ArrayList<>();
    
            //考虑特殊情况
            if(candidates==null || candidates.length<0)
                return res;
            else
            {
                Arrays.sort(candidates);
                getSum(candidates,target,res,one,0,0);
                return res;
            }
        }
    
        private void getSum(int[] candidates, int target, List<List<Integer>> res,
                List<Integer> one, int sum,int level) 
        {
            //前面两个if的判断不能互换位置，否者会报错
            if(sum==target)
                res.add(new ArrayList<>(one));
            else if(sum>target || level==candidates.length)
                return ;
            else
            {
                //题目中说可以重复的使用某一个数，所以level可以不变
                for(int i=level;i<candidates.length;i++)
                {
                    //这个过程就是剪枝，在递归之处剪枝
                    if(level!=i && candidates[i]==candidates[i-1])
                        continue;
    
                    one.add(candidates[i]);
                    //所以这里的level为i+1就是表示递归到下一层，但是得到的解可能重复
                    getSum(candidates, target, res, one, sum+candidates[i], i+1);
                    one.remove(one.size()-1);
                }
            }
    
    
        }
    
    
    }

下面是C++的做法，和上一道题一样，这是一道很经典的DFS深度优先遍历的做法，上面的Java的递归逻辑有点乱，写的很不好，其实应该这么写，一共两种临街情况，分情况讨论即可，其实还是按照index做递归

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> combinationSum2(vector<int>& can, int target)
        {
            sort(can.begin(), can.end());
            dfs(can, target, 0, 0, vector<int>());
            return res;
        }
    
        void dfs(vector<int>& can, int target, int sum, int index, vector<int> one)
        {
            if (index == can.size())
            {
                if (sum == target)
                    res.push_back(one);
                return;
            }
            else
            {
                if (sum > target)
                    return;
                else if (sum == target)
                    res.push_back(one);
                else
                {
                    for (int i = index; i < can.size(); i++)
                    {
                        //去除重复元素导致的结果重复
                        if (i > index && can[i] == can[i - 1])
                            continue;
    
                        one.push_back(can[i]);
                        dfs(can, target, sum + can[i], i + 1, one);
                        one.pop_back();
                    }
                }
            }
    
        }
    };

[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 216. Combination Sum III DFS _ _index]: http://blog.csdn.net/jackzhang_123/article/details/78059803
[leetcode 39. Combination Sum DFS]: http://blog.csdn.net/jackzhang_123/article/details/77802950