39. 组合和

给定一组不同的整数候选者和一个目标整数目标，返回所有唯一的候选者组合的列表，其中所选数字之和达到目标。您可以按任何顺序返回组合。

同一个号码可以无限次地从候选人中选择。两个组合是唯一的，如果
频率
至少有一个所选数字不同。

生成的测试用例使得对于给定输入而言，总和达到目标的唯一组合数量少于 150 个组合。

示例1：

输入：候选人 = [2,3,6,7]，目标 = 7
输出：[[2,2,3],[7]]
说明：
2和3是候选，2 + 2 + 3 = 7。注意2可以多次使用。
7 是候选者，7 = 7.
这是仅有的两种组合。
示例2：

输入：候选人 = [2,3,5]，目标 = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]
示例3：

输入：候选人 = [2]，目标 = 1
输出：[]

限制：

1
2
候选人的所有元素都是独特的。
1

原始页面

这道题和昨天解决的题差别不是很大。
BackTracking 仍然可以很好地搜索深度的可能性并使用循环进行宽度控制。
需要注意的是，这里我们可以添加相同的元素，然后保持整个组合的独特性

public List>combinationSum(int[] Candidates, int target) {
List> list = new ArrayList();
List Coms = new LinkedList();
backTracking(列表, 梳子, 候选者, 目标, 0, 0);
返回列表；
}

公共无效 backTracking（列表>列表，列表梳，int []候选人，int目标，int总和，int开始）{
    如果（总和>目标）{
        返回;
    }
    如果（总和==目标）{
        list.add(new ArrayList(combs));
        返回;
    }

    for(int i=start; i<candidates.length i backtracking sum><h2>

40. 组合和 II
    

超过时间限制

 Set> set = new HashSet();
    公共列表>组合Sum2（int []候选人，int目标）{
        List Coms = new LinkedList();
        Arrays.sort(候选);
        backTracking(combs, 目标, 候选者, 0, 0);

        返回新的 ArrayList(set);
    }

    public void backTracking(Listcombs, int target, int[]candidates, int start, int sum){
        如果（总和>目标）{
            返回;
        }
        如果（总和==目标）{
            set.add(new ArrayList(combs));
        }

        for(int i=start; i 目标){
                继续;
            }

            总和+=候选人[i]；
            梳子.add（候选者[i]）；
            backTracking(combs, 目标, 候选者, i+1, sum);
            sum -= 候选人[i];
            梳子.删除(梳子.size()-1);

        }
    }
登录后复制

因为有一些元素之前已经使用过，例如[1,1,1,2,3] 第一次递归中使用了112，但是循环会遍历从1到3开始的所有元素，并且存在三个“1”，所以当遇到第二个“1”时，组合112也会找到，这在之前的递归步骤中已经找到了，所以我们应该减少这些多余的步骤（类似地，它也可能发生在递归的遍历和递归的横向递归中。

  解决问题

 List> list = new ArrayList();
    公共列表>组合Sum2（int []候选人，int目标）{
        List Coms = new LinkedList();
        Arrays.sort(候选);
        backTracking(combs, 目标, 候选者, 0, 0, false);

        返回列表；
    }

    public void backTracking(Listcombs, int target, int[]candidates, int start, int sum, boolean Horizo??n){
        如果（总和>目标）{
            返回;
        }
        如果（总和==目标）{
            list.add(new ArrayList(combs));
        }

        for(int i=start; i 目标){
                继续;
            }

            if(i!=0 && 候选人[i] == 候选人[i-1] && 地平线){
                继续;
            }

            总和+=候选人[i]；
            梳子.add（候选者[i]）；
            backTracking(combs, 目标, 候选者, i+1, sum, false);
            sum -= 候选人[i]；
            梳子.删除(梳子.size()-1);
            地平线=真；
        }
    }
登录后复制

  131. 回文分区

给定一个字符串 s，对 s 进行分区使得每个 
子串
 分区的 是 
回文
。返回 s. 所有可能的回文划分

示例1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例2：

输入：s = "a"
输出：[["a"]]

限制：

1 
s 仅包含小写英文字母。
原始页面

 List> list = new ArrayList();
    公共列表>分区（字符串s）{
        List 梳 = new ArrayList();

        backTracking(combs, new StringBuilder(s), 0);
        返回列表；
    }

    公共无效 backTracking（List 梳子，StringBuilder str，int start）{
        if(start == str.length()){
            list.add(new ArrayList(combs));
            返回;
        }

        for(int i=1; i+start 

        登录后复制以上就是LeetCode DayBackTracking 第 2 部分的详细内容，更多请关注php中文网其它相关文章！