aboutsummaryrefslogtreecommitdiff
path: root/sum_subset_xor.c
diff options
context:
space:
mode:
Diffstat (limited to 'sum_subset_xor.c')
-rw-r--r--sum_subset_xor.c23
1 files changed, 4 insertions, 19 deletions
diff --git a/sum_subset_xor.c b/sum_subset_xor.c
index cb51647..7c32618 100644
--- a/sum_subset_xor.c
+++ b/sum_subset_xor.c
@@ -8,26 +8,11 @@
* if 'a' can be obtained from 'b' by deleting some elements of 'b'.
*/
-void backtrack(int *nums, int numsSize, int tar, int idx, int *cnt) {
- if (idx == numsSize) {
- return;
- } else {
- for (int i = idx; i < numsSize; i++) {
- tar ^= nums[i];
- *cnt += tar;
- backtrack(nums, numsSize, tar, i + 1, cnt);
- tar ^= nums[i];
- }
- }
-}
-
int subsetXORSum(int *nums, int numsSize) {
- int ans = 0;
- for (int i = 0; i < numsSize; i++) {
- ans += nums[i];
- backtrack(nums, numsSize, nums[i], i + 1, &ans);
- }
- return ans;
+ int all = 0, mult = 1 << (numsSize - 1);
+ for (int i = 0; i < numsSize; i++)
+ all |= nums[i];
+ return all * mult;
}
int main() {