526互联

求和为target的数字组合

发布时间 2023-08-17 15:51:47作者: 黄燃

题目：现给定⼀个整数数组（数组⻓度⼤于等于 5）nums 和⼀个整数⽬标值 target，请你在该数组中
找出和为⽬标值 target 的那 n（n<nums.length） 个整数，并返回它们的数组（如果有多个下标组合
都满⾜，则返回下标和最⼩的那⼀组）的下标。
注意：数组中同⼀个元素在答案⾥不能重复出现。 ⽐如输⼊：nums = [3，2，4，5，7]，n=3，
target = 10 输出：[0，1，3]

答案from ChatGPT：

        function combinationSum(nums, n, target) {
            let result = [];
            let combination = [];

            function backtrack(start, target) {
                if (target === 0 && combination.length === n) {
                    result.push([...combination]);
                    return;
                }

                for (let i = start; i < nums.length; i++) {
                    if (target < nums[i]) {
                        break;
                    }

                    combination.push(i);
                    backtrack(i + 1, target - nums[i]);
                    combination.pop();
                }
            }

            backtrack(0, target);
            return result[0];
        }