力扣刷题之旅（一） DFS相关题目

1.基于排列组合的DFS / 基于图的DFS

leetcode 698 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

class Solution {int[] nums;boolean[] visited;int per, n;public boolean canPartitionKSubsets(int[] nums, int k) {this.nums = nums;n = nums.length;int sum = 0;for(int num : nums){sum += num;} if(sum % k != 0){return false;}Arrays.sort(nums);per = sum / k;if(nums[n - 1] > per){return false;}visited = new boolean[(1 << n)];return dfs(0, 0);}private boolean dfs(int state, int cur) {// nums所有元素都选完if (state == visited.length - 1) { return true; }// 剪枝if (visited[state]) { return false;}visited[state] = true;for (int i = 0; i < nums.length; i++) {// 大于总和过界if (nums[i] + cur > per) {break; }//当前元素已被使用if (((state >> i) & 1) == 1) {continue; }// 取余的作用是当填满一个集合时，将cur重置为0boolean res = dfs(state | (1 << i), (cur + nums[i]) % per);if (res){return true;}}return false;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！