集合遍历

这道题是变相的排序题目。目的是输出0～1111,1111之间位数上的数之和为8的所有数，并从小到大排列。找到这个规律题目就好解了。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.TreeSet;

public class Main {
    private static TreeSet<String> results = new TreeSet<>();
    private static int[] colorfulBalls;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int k = Integer.parseInt(params[0]), n = Integer.parseInt(params[1]);
        colorfulBalls = new int[k];
        int[] remainBalls = new int[k];
        for(int i = 0; i < k; i++) {
            colorfulBalls[i] = Integer.parseInt(br.readLine());
            remainBalls[i] = colorfulBalls[i];
        }
        dfs(remainBalls, n, 0);
        for(String result: results){
            System.out.println(result);
        }
    }
    
    private static void dfs(int[] remainBalls, int rest, int depth) {
        if(rest == 0){     // 不需要球了，添加一个答案
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < remainBalls.length; i++){
                sb.append(colorfulBalls[i] - remainBalls[i]);
            }
            results.add(sb.toString());
        }
        if(rest > 0){
            for(int i = depth; i < remainBalls.length; i++){
                if(remainBalls[i] > 0){     // 第i个颜色还有球的时候就拿一个
                    remainBalls[i] --;
                    dfs(remainBalls, rest - 1, i);
                    remainBalls[i] ++;      // 回溯
                }
            }
        }
    }
}

import java.util.*;
/**
*  回溯算法
*/
public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        int n = scan.nextInt();    

      Map<Integer, Integer> nums = new HashMap<>();
        for (int i = 0; i < k; i++)
            nums.put(i, scan.nextInt());
                scan.close();

        traverse(new StringBuilder(), nums, 0, n);

        for (String s : result)
            System.out.println(s);
    }

    static List<String> result = new ArrayList<>();
    static int ballUsed = 0;    //记录已使用小球数量
    static boolean flag = false;

    static void traverse(StringBuilder res, Map<Integer, Integer> nums, int k, int n) {
        if (ballUsed > n) {
            flag = true;
            return;
        }
        if (k == nums.size()) {
            if (ballUsed == n)
                result.add(res.toString());
            return;
        }

        for (int i = 0; i <= nums.get(k); i++) {
            res.append(i);
            ballUsed += i;
            traverse(res, nums, k + 1, n);
            ballUsed -= i;
            res.deleteCharAt(res.length() - 1);
            if (flag) {        //剪枝，如果已使用小球超过总数n，则不再回溯
                flag = false;
                return;
            }
        }
    }
}

# coding=utf-8
import sys
a = [0]*11
ans = [0]*11
k,n=0,0

def Print(k, ans):
    res = ''
    for i in range(k):
        res += str(ans[i])
    print(res)

def fun(i, n): # i可以认为是球类比的编号，ans[i]就是结果中，i类球放几个
    if n==0:  # n=0就是递归结束了，要放的球都安排好了～
        Print(k, ans)
        return
    if n<0 or k==i:
        return
    for j in range(a[i]+1):  # a[i]+1就是j可以取0～a[i]
    # 即j表示这类球放几个
        ans[i] = j
        fun(i+1, n-j)  # i+1是移动下，考虑放下一类球了～
    ans[i] = 0  # 没遍历到的ans位就是放0个球

try:
    while True:
        line1 = sys.stdin.readline().strip()
        l = list(map(int, line1.split()))
        k = l[0]  # 球共所少类
        n = l[-1] # 共需要n个球
        nums = sys.stdin.readlines()
        # a数组，index为球的类，index上的value为这类球有的数量
        a = [int(v.strip()) for v in nums]
        fun(0, n)
except:
    pass

/*C++，AC百分之八十，测试用例运行时间:3ms，内存占用：376k，
 *采用迭代递归，有大佬看的话麻烦指点优化一下，谢谢~~~
*/
#include <iostream>
#include <vector>~~
#include<iterator>
using namespace std;

void demo(vector< vector<int> > *v, vector<int> *v1, int n, int l, int sum)
{
	if (l == n)
	{
		int sum1 = 0;
		for (unsigned int j = 0; j < l; j++)
		{
			sum1 += v1->at(j);
		}

		if (sum1 == sum)
		{
            copy(v1->begin(), v1->end(), ostream_iterator<int>(cout));
			cout << endl;
		}
		return;
	}
	
		for (unsigned int j = 0; j < v->at(l).size(); j++)
		{
			v1->at(l) = v->at(l).at(j);
			demo(v, v1, n, l + 1, sum);
		}
}

int main()
{
	int n = 0;
	int sum = 0;
	cin >> n >> sum;

	vector< vector<int> > v_int(n);

	for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;

		for (int j = 0; j <= temp; j++)
		{
			v_int.at(i).push_back(j);
		}
	}

	vector<int> temp1(n);
	demo(&v_int, &temp1, n, 0, sum);

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int k,n;
vector<int> nums;
set<string > ret;
void dfs(int index,int len,string &ans){
    if(len==n){
        ret.insert(ans);return ;
    }
    for (int i=index;i>=0;i--){
        if(nums[i]>0){
            ans[i]++,nums[i]--;
            dfs(i,len+1,ans);
            nums[i]++,ans[i]--;            
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>k>>n;
    int temp;
    for (int i=0;i<k;i++){
        cin>>temp;
        nums.push_back(temp);
    }
    string ans(k,'0');
    dfs(k-1,0,ans);
    for (auto s:ret)
        cout<<s<<endl;
}

import java.util.Scanner;
import java.util.List;
import java.util.LinkedList;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int k = sc.nextInt();
            int n = sc.nextInt();
            int[] nums = new int[k];
            for(int i = 0;i < k; i++){
                nums[i] = sc.nextInt();
            }
            
            List<String> result = new LinkedList<>();
            help(result,n,0,nums,"");
            result.forEach(System.out::println);
        }
    }
    
    protected static void help(List<String> result,int target,int start,int[] nums,String s){
        if(target == 0 && start == nums.length){
            result.add(s);
            return;
        }
        
        if(start == nums.length){
            return;
        }
        for(int i = 0;i <= Math.min(target,nums[start]);i++){
            // 取当前 target 和对应球的数量中的较小值。
            help(result,target - i,start+1,nums,s+i);
        }
    }
}

用一个recursion可以解决，每次在每个位置放上可能的值，在最后检查该解是否符合题目要求（总和为n）

#include 
#include 
#include 
#include 

using namespace std;

void printVec(vector v)
{
    for (auto x : v)
        cout << x;
    cout << endl;
}

void solve(vector temp, vector b, int index, int r)
{
    if (index == temp.size())
    {
        if (r == 0)
            printVec(temp);
        return;
    }
    for (int i = 0; i <= min(b[index], r); i++)
    {
        temp[index] = i;
        solve(temp, b, index + 1, r - i);
    }
}

int main() 
{
    int k, n;
    cin >> k >> n;
    vector balls (k);
    for (int i = 0; i < k; i++)
        cin >> balls[i];
    vector v (k, 0);
    solve(v, balls, 0, n);
}

// 回溯
function two(kindN, selectN, arr) {
    let ans = []
    function backup(k, target, subans) {
        if (target < 0) return
        if (k == kindN && target == 0) {        
            ans.push([...subans]);
        }

        for (let i=0; i<=arr[k]; i++) {
            subans.push(i);
            backup(k+1, target-i, subans);
            subans.pop();
        }
    }

    backup(0, selectN, []);
    return ans
}

var line;
while (line=readline()) {
    let tmp = line.split(' ');
    let K = parseInt(tmp[0]), T = parseInt(tmp[1]);
    let Arr = [];
    for (let i=0; i<K; i++) {
        Arr.push(parseInt(readline()))
    }
    
    let ans = two(K, T, Arr);
    for (let i=0; i<ans.length; i++) {
        console.log(ans[i].join(''));
    }
}

c++ dfs AC100

#include 
(849)#include 
using namespace std;
void dfs(vector a, int n, int index, vector res)
{
    if (index < a.size() - 1)
    {
        for (int i = 0; i <= a.at(index); i++)
        {
            if (i <= n)
            {
                res[index] = i;
                dfs(a, n - i, index + 1, res);
            }
        }
    }
    else
    {
        if (n <= a.at(index))
        {
            res[index] = n;
            for (int k = 0; k < res.size(); k++)
                cout << res.at(k);
            cout << endl;
        }
    }
    return;
}
int main()
{
    int K, N, i;
    cin >> K >> N;
    vector a;
    for (int j = 0; j < K; j++)
    {
        cin >> i;
        a.push_back(i);
    }
    int index = 0;
    vector res;
    for (int j = 0; j < K; j++)
    {
        res.push_back(0);
    }
    dfs(a, N, index, res);
    return 0;
}

public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int k=sc.nextInt();
            int n=sc.nextInt();
            int [] nums=new int[k];
            for(int i=0;i<k;i++){
                nums[i]=sc.nextInt();
            }
            Stack<String> stack=new Stack<String>();
            helper(nums,n,0,stack,"");
            while(!stack.isEmpty()){
            System.out.println(stack.pop());
            }
        }
        
    }
    private static void helper(int [] nums,int target,int index,Stack<String> stack,String string){
        if(index==nums.length&&target==0){
            stack.push(string);
            return;
        }
        int nextTarget=0;
        for(int i=Math.min(target,nums[index]);i>=0;i--){
            nextTarget=target-i;
            helper(nums,nextTarget,index+1,stack,string+"i");
        }
    }