加起来和为目标值的组合(三)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param n int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> res;
    vector<int>path;
    void backtracking(int targetsum,int k,int sum,int startindex){
        if(sum>targetsum)return ;
        if(path.size()==k){
            if(sum==targetsum){
                res.push_back(path);
                return ;
            }
        }
        
        for(int i=startindex;i<=9-(k-path.size())+1;i++){
            sum+=i;
            path.push_back(i);
            backtracking(targetsum,k, sum,i+1);
            sum-=i;
            path.pop_back();
        }
    }
    vector<vector<int> > combination(int k, int n) {
        // write code here
        res.clear();
        path.clear();
        backtracking(n,k, 0,1);
        return res;
    }
};

class Solution {
  public:
     vector<vector<int>> res;
    vector<int> path;
    void dfs(int k, int n, int cur_sum, int index) {
        if (path.size() == k && cur_sum == n) {
            res.push_back(path);
            return;
        }
        for (int i = index; i <= 9 ; i++) {
            path.push_back(i);
            cur_sum += i;
            dfs(k, n, cur_sum, i + 1);
            cur_sum -= i;
            path.pop_back();
        }
    }
    vector<vector<int> > combination(int k, int n) {
        dfs(k, n, 0, 1);
        return res;
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param k int整型 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def combination(self , k: int, n: int) -> List[List[int]]:
        # write code here
        res = []
        self.traverse([], k, n, res)

        return res

    def traverse(self, tmp, k, target, res):
        if k == len(tmp) and target == 0:
            res.append(tmp.copy())
            return

        if len(tmp) >= k:
            return

        start = 1
        if len(tmp) != 0:
            start = tmp[-1] + 1
        for i in range(start, 10):
            if i in tmp:
                continue

            if i >target:
                break
            
            tmp.append(i)
            self.traverse(tmp, k, target-i, res)
            tmp.pop()

回溯+剪枝。超过K个数的结果直接丢弃

import java.util.*;
public class Solution {
    List<List<Integer>> res;
    public int[][] combination (int k, int n) {
        int nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        res = new ArrayList<>();
        func(k, n , new ArrayList<Integer> (), nums, 0, 0);
        int[][] r = new int[res.size()][k];
        res.sort(new Comparator<List<Integer>> () {
            public int compare(List<Integer> list1, List<Integer> list2) {
                for(int i = 0; i < list1.size(); ++i) {
                    if(list1.get(i) != list2.get(i)) {
                        return list1.get(i) - list2.get(i);
                    }
                }
                return 0;
            }
        });
        for(int i = 0; i < res.size(); ++i) {
            if(res.get(i).size() != k) continue;
            for(int j = 0; j < res.get(i).size(); ++j) {
                r[i][j] = res.get(i).get(j);
            }
        }
        return r;
    }
    public void func(int k, int n, ArrayList<Integer> list, int[] nums, int cur, int index) {
        if(list.size() > k) return;
        if(cur == n) {
            if(list.size() == k)
                res.add(new ArrayList<>(list));
            return;
        } else if(cur > n || index >= 9) return;
        func(k, n, list, nums, cur, index + 1);
        list.add(nums[index]);
        func(k, n, list, nums, cur + nums[index], index + 1);
        list.remove(list.size() - 1);
    }
}

function combination( k , n ) {
// write code here
const res = []
const fn = (i, path) => {
path.push(i)
let sum = path.reduce((s, val) => s += val, 0)
if (sum > n) {
return
}
if (path.length == k && sum == n) {
res.push([...path])
return
}

    for (let j = i + 1; j < n; j++) {
        fn(j, path)
        path.pop()
    }
}
for (let i = 1; i < n; i++) {
    fn(i, [])
}
return res

}

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param k int整型 
 * @param n int整型 
 * @return int整型二维数组
*/
func combination( k int ,  n int ) [][]int {
    ans:=[][]int{}
    var back_tracking func([]int,int,int)
    back_tracking=func(path []int,sum int,idx int){
        if sum>=n{
            if len(path)==k&&sum==n{
                tmp:=make([]int,len(path))
                copy(tmp,path)
                ans=append(ans,tmp)
            }
            return
        }
        if len(path)>k{
            return
        }
        for i:=idx;i<n;i++{
            path=append(path,i)
            sum+=i
            back_tracking(path,sum,i+1)
            path=path[:len(path)-1]
            sum-=i
        }
    }
    back_tracking([]int{},0,1)
    return ans
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param k int整型
     * @param n int整型
     * @return int整型二维数组
     */
    private ArrayList<ArrayList> list_1109 = new ArrayList<>();

    private void dfs(int[] arr, ArrayList<Integer> list, int size, int target,
                     int sum, int index) {
        if (list.size() == size) {
            if (sum == target) {
                list_1109.add(new ArrayList(list));
            }
            return;
        }
        for (int i = index; i < arr.length; i++) {
            list.add(arr[i]);
            sum = sum + arr[i];
            dfs(arr, list, size, target, sum, i + 1);
            list.remove(list.size() - 1);
            sum = sum - arr[i];
        }
    }

    public int[][] combination(int k, int n) {
        int[] arr = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
        ArrayList<Integer> list = new ArrayList<>();
        dfs(arr, list, k, n, 0, 0);
        int[][] res = new int[list_1109.size()][];
        for (int i = 0; i < res.length; i++) {
            final ArrayList arrayList = list_1109.get(i);
            res[i] = new int[arrayList.size()];
            for (int j = 0; j < arrayList.size(); j++) {
                res[i][j] = (int) arrayList.get(j);
            }
        }
        return res;
    }
}

function combination( k ,  n ) {
    let res = [];
    let path = [];
    backTracking(k, n, 0, 1);
    return res;
    
    function backTracking(k, n, sum, startIndex){
        if(path.length === k && sum === n){
            res.push([...path]);
            return;
        }
        if(sum > n){
            return;
        }
        for(let i = startIndex; i < n - (k - path.length) + 1; i++){
            sum += i;
            path.push(i);
            backTracking(k, n, sum, i + 1);
            sum -= i;
            path.pop();
        }
    }
}

主要实现还是回溯迭代方法。主要考虑回溯点的位置，确定界点

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param k int整型 
 * @param n int整型 
 * @return int整型二维数组
 */
function combination( k ,  n ) {
    // write code here
    dfcData(1, k, n, [])
    return resultArr
//     console.log(JSON.stringify(resultArr))
}
var resultArr = []
function dfcData(i, k, n, arr) {
   if(k < 0 || n < 0) {
       return;
   }
    if(n === 0 && k ===0) {
        const arrtemp = [...arr]
        resultArr.push(arrtemp)
        return;
    }
    for(let a = i; a <= 9; a++) {
        arr.push(a)
        dfcData(a+1, k-1, n-a, arr)
        arr.pop()
    }
}
module.exports = {
    combination : combination
};

class Solution {
public:
    vector<vector<int>>tmp;vector<int>list;
    void dfs(int start,int k,int sum)
    {
        if(sum<=0){if(list.size()==k&&sum==0)tmp.push_back(list);}
         for(int i=start;i<=9;i++)
         {
             list.push_back(i);
             dfs(i+1,k,sum-i);
             list.pop_back();
         }
    }
    vector<vector<int> > combination(int k, int n) {
        dfs(1,k,n);
        return tmp;
    }
};