面试算法81:允许重复选择元素的组合

2024-01-03 19:45:09

题目

给定一个没有重复数字的正整数集合,请找出所有元素之和等于某个给定值的所有组合。同一个数字可以在组合中出现任意次。例如,输入整数集合[2,3,5],元素之和等于8的组合有3个,分别是[2,2,2,2]、[2,3,3]和[3,5]。

分析

能够用回溯法解决的问题都能够分成若干步来解决,每一步都面临若干选择。对于从集合中选取数字组成组合的问题而言,集合中有多少个数字,解决这个问题就需要多少步。每一步都从集合中取出一个下标为i的数字,此时面临两个选择。一个选择是跳过这个数字不将该数字添加到组合中,那么这一步实际上什么都不做,接下来处理下标为i+1的数字。另一个选择是将数字添加到组合中,由于一个数字可以重复在组合中出现,也就是说,下一步可能再次选择同一个数字,因此下一步仍然处理下标为i的数字。

public class Test {
    public static void main(String[] args) {
        int[] nums = {2, 3, 5};
        List<List<Integer>> result = combinationSum(nums, 8);
        for (List<Integer> item : result) {
            System.out.println(item);
        }
    }

    public static List<List<Integer>> combinationSum(int[] nums, int target) {
        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
        helper(nums, target, 0, combination, result);

        return result;
    }

    private static void helper(int[] nums, int target, int i, LinkedList<Integer> combination,
        List<List<Integer>> result) {
        if (target == 0) {
            result.add(new LinkedList<>(combination));
        }
        else if (target > 0 && i < nums.length) {
            helper(nums, target, i + 1, combination, result);

            combination.add(nums[i]);
            helper(nums, target - nums[i], i, combination, result);
            combination.removeLast();
        }
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135337633
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。