有个物品可供选择,必须选择其中个物品,请按字典序顺序输出所有选取方案的物品编号
与与等被认为是同一种方案,输出字典序最小的即可
数据范围:
进阶:时间复杂度,空见复杂度
有个物品可供选择,必须选择其中个物品,请按字典序顺序输出所有选取方案的物品编号
对于每一组测试数据, 每行输入个数和。
对于每组输入样例,按字典序输出所有方案选择物品的编号,每种方案占一行
4 1
1 2 3 4
5 2
1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.Stack; public class Main { public static ArrayList<Stack<Integer>> res = new ArrayList<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().trim().split(" "); int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]); dfs(n, m, 1, new Stack<Integer>()); for(Stack<Integer> stack: res){ for(Integer elem : stack) System.out.print(elem + " "); System.out.println(); } } private static void dfs(int n, int m, int depth, Stack<Integer> stack) { if(stack.size() == m){ res.add((Stack<Integer>)stack.clone()); return; } for(int i = depth; i <= n; i++){ stack.push(i); dfs(n, m, i + 1, stack); stack.pop(); } } }再来个scala版本的,由于栈是先进后出,因此在将栈变为数组的时候需要进行反转才能保持原先栈底到栈顶的顺序
import scala.io.StdIn import scala.collection.mutable._ object Main { def main(args: Array[String]): Unit = { val params: Array[String] = StdIn.readLine().split(" ") val n = params(0).toInt val m = params(1).toInt val res = ListBuffer[Array[Int]]() dfs(1, n, m, Stack[Int](), res) res.foreach((row: Array[Int]) => println(row.mkString(" "))) } def dfs(depth: Int, n: Int, m: Int, combination: Stack[Int], res: ListBuffer[Array[Int]]): Unit = { if(combination.size == m){ res.append(combination.toArray.reverse); return } for(i <- depth to n){ combination.push(i) dfs(i + 1, n, m, combination, res) combination.pop } } }
#include<bits/stdc++.h> using namespace std; vector<int> path; void backtracking(int n, int m, int startIndex){ if(path.size() == m){ for(int i = 0; i < m; i++){ cout << path[i] << " "; } cout << endl; return; } for(int i = startIndex; i <= n; i++){ if(n - i + 1 < m - path.size()) break;//剪枝 path.push_back(i); backtracking(n, m, i + 1); path.pop_back(); } } int main(){ int n, m; while(cin >> n >> m){ backtracking(n, m, 1); } }
正常dfs模板题
但是介于本人不会, 所以选择了暴力一点的方式
import java.lang.*; import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); for(int a = 1; a <= n; ++ a) { if(m > 1) for(int b = a + 1; b <= n; ++ b ) if(m > 2) for(int c = b + 1; c <= n; ++ c) if(m > 3) for(int d = c + 1; d <= n; ++ d) if(m > 4) for(int e = d + 1; e <= n; ++ e) if(m > 5) for(int f = e + 1; f <= n; ++ f) if(m > 6) for(int h = f + 1; h <= n; ++ h) if(m > 7) for(int i = h + 1; i <= n; ++ i) if(m > 8) for(int j = i + 1; j <= n; ++ j) if(m > 9) for(int k = j + 1; k <= n; ++ k) if(m > 10) for(int l = k + 1; l <= n; ++ l) if(m > 11) for(int o = l + 1; o <= n; ++ o) System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j+" "+k+" "+l+" "+o); else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j+" "+k+" "+l); else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j+" "+k); else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i+" "+j); else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h+" "+i); else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+h); else System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f); else System.out.println(a+" "+b+" "+c+" "+d+" "+e); else System.out.println(a+" "+b+" "+c+" "+d); else System.out.println(a+" "+b+" "+c); else System.out.println(a+" "+b); else System.out.println(a); } } }
#include <iostream> #include <vector> using namespace std; #define int long long vector<int> ans; int m, n; void dfs(int l) { // if(l > n) return; if(ans.size() == m) { for(int a : ans) cout << a << " "; cout << endl; } for(int i = l; i <= n; ++ i) { ans.push_back(i); dfs(i+1); ans.pop_back(); } } signed main() { cin >> n >> m; dfs(1); }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[] stack = new int[m]; int i; for (i = 0; i < m; i++) { stack[i] = i + 1; } int bot = stack[0]; while (bot + m <= n) { for (i = 0; i < m; i++) { System.out.print(stack[i] + " "); } System.out.println(); for (i = m - 1; i >= 0; i--) { if (stack[i] + 1 <= n && m - 1 - i + stack[i] + 1 < n + 1) { stack[i] += 1; break; } } i++; for (; i < m ; i++) { stack[i] = stack[i - 1] + 1; } bot = stack[0]; } for (i = 0; i < m; i++) { System.out.print(stack[i] + " "); } System.out.println(); } }
//说实话,不太明白为啥不对,有大佬能解答一下吗 import java.util.Random; public class DOM { static Random a1 = new Random(); // static int m = a1.nextInt(20)+1; // static int n = a1.nextInt(m)+1; static int m=10; static int n=3; static int[]a=new int[m]; static int[] b = new int[n]; public static void C(int m,int n){ for(int i=n;i<=m;i++) { b[n-1] = i-1; if(n>1) C(i-1,n-1); else { for(int j=0;j<DOM.n;j++){ System.out.print(a[b[j]] + " "); } System.out.println(); } System.out.println(); } } public static void main(String[] args){ System.out.println(m); System.out.println(n); for (int i = 0; i <m ; i++) { a[i]=i+1; } C(m,n); } }
track = [] def trackback(i,targetnum): if len(track) == target_num: for i in range(len(track)): print(track[i],end =" ") print() for k in range(i,len(data)): track.append(data[k]) trackback(k+1, targetnum) track.pop() if __name__ == "__main__": num = list(map(int,input().split())) target_num = num[1] data = [] for i in range(num[0]): data.append(i+1) trackback(0,target_num)
#include <iostream> using namespace std; int a[15]; bool st[15]; int n,m; void dfs(int x,int t){ if(t == x + 1){ for(int j = 1;j <= x;j++)cout<<a[j]<<" "; cout<<endl; return; } for(int i = 1;i <= n;i++){ if(!st[i] && i > a[t-1]){ st[i] = true; a[t++] = i; dfs(x,t); t--; st[i] = false; } } } int main(){ cin>>n>>m; dfs(m,1); return 0; }简单的dfs
#include <iostream> #include <vector> using namespace std; void dfs(int n, int m, int i, int j, vector<vector<int>>& ans, vector<int>& temp){ if(j == m){//j记录在temp中已有几个数,满了就插入答案数组 ans.push_back(temp); return; } for(int k = i; k <= n; k++){ temp.push_back(k); dfs(n, m, k + 1, j + 1, ans, temp);//选择的下一个数从k+1开始,避免重复 temp.pop_back(); } } int main(){ ios::sync_with_stdio(false); int n, m; vector<vector<int>> ans;//ans存储全部方案 vector<int> temp;//temp临时存储一种方案 cin >> n >> m; dfs(n, m, 1, 0, ans, temp); for(size_t i = 0; i < ans.size(); i++){ for(size_t j = 0; j < ans[0].size(); j++){ cout << ans[i][j] << " "; } cout << endl; } return 0; }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String[] str=br.readLine().trim().split(" ");; int n=Integer.parseInt(str[0]); int m=Integer.parseInt(str[1]); List<Integer> list=new ArrayList<>(); getAns(list,0,0,n,m); } public static void getAns(List<Integer> list,int index,int count,int n,int m){ if(count==m){ for(int i=0;i<list.size()-1;i++){ System.out.print(list.get(i)+" "); } System.out.println(list.get(list.size()-1)); return; } if(index==n)return; if(m-count>n-index)return; list.add(index+1); getAns(list,index+1,count+1,n,m); list.remove(list.size()-1); getAns(list,index+1,count,n,m); } }
line = input().split() n, m = int(line[0]), int(line[1]) def dfs(state, cur): if len(cur)==m: print(' '.join(cur)) return for i in range(1, n+1): cur_state = 1<<(i-1) if cur_state&state&nbs***bsp;(cur and i<int(cur[-1])): continue dfs(state|cur_state, cur+[str(i)]) dfs(0, [])dfs+状态压缩
def func(nums): track = [] n = len(nums) def backtrack(index=0): if len(track) == target_num: for x in track: print(x, end=" ") print() for i in range(index, n): track.append(nums[i]) backtrack(i + 1) track.pop() backtrack() row_one = list(map(int, input().split())) nums = [i + 1 for i in range(row_one[0])] target_num = row_one[1] func(nums)
def dfs(curr, start, n, k): if len(curr) == k: # 由于ret里面存的是curr的引用,下一层递归对curr的修改会影响ret里面的结果, # 所以要把curr里面的值拷贝出来,用copy() ret.append(curr.copy()) # 注意解除引用 return for i in range(start, n+1): dfs(curr+[i], i+1, n, k) return n,k = map(int, input().split()) curr = [] ret = [] dfs(curr,1,n,k) for i in ret: for j in i: print(j,end=' ') print()
终于有一道我能做的题了,,,
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; public class Main { public static ArrayList> res = new ArrayList(); public static ArrayList path = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().trim().split(" "); int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]); dfs(n, m, 1); for(ArrayList items: res){ for(Integer elem : items){ System.out.print(elem + " "); } System.out.println(); } } private static void dfs(int n, int m, int index) { if(path.size() == m){ res.add(new ArrayList(path)); return; } for(int i = index; i <= n; i++){ path.add(i); dfs(n, m, i + 1); path.remove(path.size() - 1); } } }
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class Main { static List<int[]> list = new ArrayList<>(); public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); dfs(0, n, m, new int[m]); for (int[] arr : list) { for(int i=0; i<m; i++){ System.out.print(arr[i]); if(i < m-1){ System.out.print(" "); } } System.out.println(); } } public static void dfs(int index, int n, int m, int[] arr){ if(index==m){ int[] tmp = Arrays.copyOf(arr, m); list.add(tmp); return; } for (int i = 1; i <= n; i++) { if (index-1>=0 && arr[index-1]>=i){ continue; } arr[index] = i; dfs(index+1, n, m, arr); arr[index] = 0; } } }
#include <iostream> #include <vector> using namespace std; void dfs(vector<vector<int>>& ans, vector<int>& tmp, int& n, int m, int pos) { if(m == 0) { ans.push_back(tmp); return; } else { for(int i = pos; i <= n; i++) { tmp.push_back(i); dfs(ans, tmp, n, m - 1, i + 1); tmp.pop_back(); } } } int main() { int n, m; while(cin >> n >> m) { vector<vector<int>> ans; vector<int> tmp; dfs(ans, tmp, n, m, 1); for(const auto& e : ans) { for(const auto& q : e) { cout << q << " "; } cout << endl; } } return 0; }
#include<iostream> using namespace std; bool count_ones(int& num, int& m) { int tmp = num; int ret = 0; for (; tmp != 0;) { if (tmp % 2) ret++; tmp = tmp >> 1; } if (ret == m) return true; return false; } int main() { int n, m; cin >> n >> m; for (int i = (1 << n); i >= 1; i--) { if (count_ones(i, m)) { int cnt = 0; for (int p = 1; p <= n; p++) { if (i & (1 << (n - p))){ cnt++; if(cnt == m) cout << p << endl; else cout << p << ' '; } } } } return 0; }