LCR 157. 套餐内商品的排列顺序
class Solution {
List<String> res = new LinkedList<>();
char[] arr;
public String[] goodsOrder(String goods) {
arr = goods.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == arr.length - 1) {
res.add(String.valueOf(arr)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < arr.length; i++) { //遍历当前位置 x 到字符数组结尾的所有字符
if(set.contains(arr[i])) continue; // 重复,因此剪枝
set.add(arr[i]);
swap(i, x); // 交换,将 arr[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
原文地址:https://blog.csdn.net/qq_61504864/article/details/136395522
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!