package sftp;import java.util.*;public class Dfs { public static void main(String[] args) {// int[] count={1,2,3};// dfs(count,0,new int[3],0,3); Entity[] entities = new Entity[3]; entities[0] = new Entity(); entities[0].str = "A"; entities[0].count = 1; entities[1] = new Entity(); entities[1].str = "B"; entities[1].count = 2; entities[2] = new Entity(); entities[2].str = "C"; entities[2].count = 3;// px2(entities); dfs(entities,0,new int[3],0,3);// pailie(entities,0,0,new String[6],new int[3][3]); } public static void dfs(Entity[] count, int n, int[] use, int sum, int max) { if (n >= count.length) { if (sum == max) {// for(int i=0; i res = new ArrayList<>(); for (int i = 0; i < use.length; ++i) { if (use[i] > 0) { Entity entity = new Entity(); entity.count = use[i]; entity.str = count[i].str; res.add(entity); } } Entity[] newARR = new Entity[res.size()]; res.toArray(newARR); pailie(newARR, 0, 0, new String[max], new int[100][100]); System.out.println(); System.out.println(); } return; } for (int i = 0; i <= count[n].count; ++i) { if (sum + i <= max) { use[n] = i; dfs(count, n + 1, use, sum + i, max); } } } public static void pailie(Entity[] entities, int m, int n, String[] showArr, int[][] state) { if (m == entities.length) { for (String s : showArr) { System.out.print(s); } System.out.println(); } if (n == 0) { for (int i = 0; i < showArr.length; ++i) { if (showArr[i] == null) { state[m][0] = i; showArr[i] = entities[m].str; if (n == entities[m].count - 1) { pailie(entities, m + 1, 0, showArr, state); } else { pailie(entities, m, n + 1, showArr, state); } showArr[i] = null; } } } else { for (int i = state[m][n - 1] + 1; i < showArr.length; ++i) { if (showArr[i] == null) { showArr[i] = entities[m].str; state[m][n] = i; if (n == entities[m].count - 1) { pailie(entities, m + 1, 0, showArr, state); } else { pailie(entities, m, n + 1, showArr, state); } showArr[i] = null; } } } } public static void px2(Entity[] entities) { int arrLength = 0; Map map = new HashMap<>(); for (int i = 0; i < entities.length; ++i) { arrLength += entities[i].count; } int[] arr = new int[arrLength]; int index = 0; for (int i = 0; i < entities.length; ++i) { map.put(i, entities[i]); for (int j = 0; j < entities[i].count; ++j) { arr[index++] = i; } } print(arr, map); int currentIndex = arrLength - 2; while (currentIndex >= 0) { Integer nextIndex = getNextIndex(arr, currentIndex + 1, arrLength - 1, arr[currentIndex]); if (nextIndex == null) { currentIndex--; } else { int temp = arr[currentIndex]; arr[currentIndex] = arr[nextIndex]; arr[nextIndex] = temp; Arrays.sort(arr, currentIndex + 1, arr.length); print(arr, map); currentIndex = arrLength - 2; } } } public static void print(int[] arr, Map map) { for (int i = 0; i < arr.length; ++i) { System.out.print(map.get(arr[i]).str); } System.out.println(); } private static Integer getNextIndex(int[] arr, int i, int j, int curr) { int min = Integer.MAX_VALUE; Integer minIndex = null; for (int k = i; k <= j; ++k) { if (arr[k] > curr && arr[k] < min) { min = arr[k]; minIndex = k; } } return minIndex; } public static class Entity { int count; String str; }}